月度归档:2019年04月

NOIP2009 -HanKSon的趣味题


题意:
有n个询问,在每个询问中,先给定四个自然数a,b,c,d,然后求出有多少个x满足\( gcd(a,x)=b\) 并且\(lcm(c,x)=d\). 数据范围:\(n<=2000,1<=a,b,c,d<=2*10^9\).

Solution:
这道题有多种办法:题解

一开始尝试暴力解法,枚举d的约数,然后直接判断是否符合题目的两个条件,最后一组数据果然超时了.然后书上还有通过质因子构造约数的方法,还未尝试过.在网上看题解时发现暴力解法还可以优化,主要是要想到下面这条性质来加速GCD运算:
对两个正整数\(a,b\),设 \(gcd(a,b)=k\),则有 \(gcd(a/k,b/k)=1\).

明天写一下其他思路. 还是太菜了啊,抓紧学习啊!

暴力优化法:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;
#define MAX_N 2e9

typedef long long ll;
typedef unsigned long long ull;

int gcd(int a, int b) {
  if (b) return gcd(b, a % b);
  return a;
}

int main() {
  int n;
  cin >> n;
  while (n--) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int ans = 0;
    for (int i = 1; i*i <= d; i++) {
      if(d%i==0){
          if (i%b==0&&gcd(a/b, i/b) == 1&& gcd(d/i,d/c)==1) {
             ans++;
          }
          int j=d/i;
          if(j!=i){
              if(j%b==0&&gcd(a/b,j/b)==1&& gcd(d/j,d/c)==1){
                  ans++;
              }
          }
      }
    }
    cout<<ans<<endl;
  }

  return 0;
}

BZOJ 1257-余数之和

题目:

给定正整数 \(n\)和 \(k\),计算\((k\mod 1)+(k\mod 2)+...+(k\mod n)\)的值.\(1<=n,k<=10^9\).

思路:
直接暴力求果断TLE了.所以需要适当转化,降低时间复杂度.

整个式子可以转化为\( n*k-\sum_{i=1}^n\lfloor k/i\rfloor *i\) .

对于任意整数 \( x\in [1,k]\),设 \(g(x)=\lfloor k/\lfloor k/x\rfloor \rfloor\),有\(g(x)>=\lfloor k/(k/x)\rfloor =x\), 故\( \lfloor k/g(x)\rfloor <=\lfloor k/x \rfloor\).
另有,\(\lfloor k/g(x) \rfloor >=\lfloor k/(k/\lfloor k/x \rfloor ) \rfloor = \lfloor k/k* \lfloor k/x \rfloor \rfloor = \lfloor k/x \rfloor \) ,故\( \lfloor k/g(x) \rfloor =\lfloor k/x \rfloor \).

所以,\( \forall i \in [x,\lfloor k/ \lfloor k/x \rfloor \rfloor ],\lfloor k/i \rfloor \) 的值都相等.

\( \forall i \in [1,k] ,\lfloor k/i \rfloor \) 至多只有\(2*\sqrt{k}\)个不同的值.当\( i<= \sqrt{k}\) 时, \( \lfloor k/i \rfloor \)至多只有 \( \sqrt{k} \)个不同的值,而当\( i> \sqrt{k} \)时, \( \lfloor k/i \rfloor < \sqrt{k} \) ,故\( \lfloor k/i \rfloor \)也至多只有 \( \sqrt{k} \)个不同的值.

综上所述,对于 \( i \in [1,k] \) ,\( \lfloor k/i \rfloor \)由不超过\( 2*\sqrt{k} \)段组成,每一段 \( i \in [x, \lfloor k/ \lfloor k/x \rfloor \rfloor] \)中 \(\lfloor k/i \rfloor\)的值都等于\(\lfloor k/x \rfloor\). \( i*\lfloor k/i \rfloor\) 在段中,就是公差为\( \lfloor k/x \rfloor \)的等差数列.
整个算法时间复杂度为O(\(\sqrt{k}\)).

代码:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;
#define MAX_N 2e9

typedef  long long ll;
typedef  unsigned long long ull;

int main() {
  ll n ,k;
  cin>>n>>k;
  ll ans=n*k;;
  for(ll l=1,r;l<=n;l=r+1){
     r=k/l? min(k/(k/l),n):n;
     ans-=(k/l)*(l+r)*(r-l+1)/2;
  }
  cout<<ans<<endl;
  return 0;
}

BZOJ 1053-反素数


题目:

对于任何正整数x,其约数的个数记作\(g(x)\)。例如\(g(1)=1\)、\(g(6)=4\)。如果某个正整数x满足:\(g(x)>g(i)\) \((0<i<x)\),则称x为反质数。例如,整数 \(1,2,4,6\)等都是反质数。现在给定一个数 \(N(1<=N<=2*10^9)\),求出不超过N的最大的反质数.

思路:
引理1: 1~N中最大的反质数,就是1~N中约数个数最多的数中最小的一个.(由定义易得)
引理2: 1~N中任何数的不同质因子都不会超过10个,且所有质因子的指数总和不超过30.
\((2*3*5*7*11*13*17*19*23*29*31>2*10^9\),即使只包含最小的质数,仍有 \(2^{31}>2*10^9)\)
引理3:x为反质数的必要条件是,x可写作\(2^{c_1}*3^{c_2}*5^{c_3}*7^{c_4}*11^{c_5}*13^{c_6}*17^{c_7}*19^{c_8}*23^{c9}*29^{c{10}}\),并且\(c_1>=c2>...>=c{10}>=0\) (由反证法可得)
综上,可通过dfs求出各个\(c_1,c_2...c_n\) ,搜索过程中根据上述限制要求进行剪枝。
约数个数为\((c_1+1)*(c_2+1)*...*(cn+1)=\prod{i=1}^{n}(c_i+1)\) .
由引理1确定最后结果。

代码:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;
#define MAX_N 2e9

typedef  long long ll;
typedef  unsigned long long ull;

int prime[12]={2,3,5,7,11,13,17,19,23,29,31};
ll ans;
ll acnt;
ll n;

void dfs(ll x,ll cnt,int step){
    if(step==11){
       if((x>ans&&cnt>acnt)||x<=ans&&cnt>=acnt){
          acnt=cnt;
          ans=x;
       }
       return ;
    }
    ll P=1;
    for(int i=0;i<31;i++){
      if(x*P>n) break;
      dfs(x*P,cnt*(i+1),step+1);
      P*=prime[step];
    }
}

int main() {
  cin>>n;
  dfs(1,1,0);
  printf("%d\n",ans);
  return 0;
}

CH 3101-阶乘分解

题目:

给定整数 N(1≤N≤10^6),试把阶乘 N! 分解质因数,按照算术基本定理的形式输出分解结果中的p_i 和 c_i 即可。

思路:
如果直接分别对2~N分解质因数,再将结果合成,那么时间复杂度过高会超时。显然N!的质因数不会超过N,那么先求出不超过N的所有素数p,再分别求出其在N!中的次数。对每一个素数p,其在N!中的次数等于在1~N中的次数之和。1~N中能被p整除的有⌊N/p⌋个数,能被p^2整除的有⌊N/p^2⌋个数(也就是说此时p的次数至少有⌊N/p⌋+⌊N/p^2⌋,其中⌊N/p^2⌋不必乘以2,因为被p^2整除的数也被p整除,而此前已经统计过一次p),以此类推,p的次数就有⌊N/p⌋+⌊N/p^2⌋+⌊N/p^3⌋+……+⌊N/p^⌊log(N)/log(p)⌋⌋. 每如此计算一次,时间复杂度为O(logN),则总复杂度为O(NlogN).

代码:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;
#define MAX_N 1000005

int v[MAX_N];
int prime[MAX_N];
int c[MAX_N];

int m;
void primes(int n) {
  m = 0;
  memset(v, 0, sizeof(v));
  memset(prime, 0, sizeof(prime));
  for (int i = 2; i <= n; i++) {
    if (v[i] == 0) {
      v[i] = i;
      prime[++m] = i;
    }
    for (int j = 1; j <= m; j++) {
      if (prime[j] > v[i] || prime[j] > n / i) {
        break;
      }
      v[i * prime[j]] = prime[j];
    }
  }
}

int main() {
  int n;
  cin >> n;
  primes(n);
  for (int i = 1; i <= m; i++) {
    long long p = prime[i]; //最后一次极限情况相乘可能溢出所以用ll,有点坑,找了好久
    int t = 0;
    while (n/p) {
      t += n / p;
      p *= prime[i];
    }
    c[i] = t;
  }
  for (int i = 1; i <= m; i++) {
    printf("%d %d\n", prime[i], c[i]);
  }

  return 0;
}

POJ 2689 -Prime Distance(区间筛素数)

题目链接:POJ-2689

大致题意:给出 L,U (1<=L<U<=2147483647,U-L<=10^6),找出区间[L,U]中相邻两个质数的差最大是多少,最小是多少。

思路:关键是求出[L,U]内的所有质数,然后一趟比较即可得出结果。线性筛法和Eratosthenes筛法都可求出1~N内的所有质数,而这里U值上界可达2^31,所以即使用线筛也会超时(限制1s,大约是10^7次计算)。但注意到U-L只有10^6,考虑到每个合数都存在一个不超过n^0.5的质因子,我们求出[2,U^0.5]内的所有质数,对其中每个质数p,把[L,U]内能被p整除的数剔除,剩下的就是[L,U]的质数了。

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define MAX_N 1000005

int prime1[MAX_N];
ll prime2[MAX_N];
int m;
int v[MAX_N];

void primes(int n) {
    memset(v,0,sizeof(v));
    memset(prime1,0,sizeof(prime1));
    m=0;
    for(int i=2; i<=n; i++) {
        if(v[i]==0) {
            v[i]=i;
            prime1[++m]=i;
        }
        for(int j=1; j<=m; j++) {
            if(v[i]<prime1[j]||i>n/prime1[j]) {
                break;
            }
            v[i*prime1[j]]=prime1[j];
        }
    }
}

int main() {
    ll L, U;
    primes(sqrt(2147483647)); //预处理
    while(cin>>L>>U) {
        memset(v,0,sizeof(v));
        memset(prime2,0,sizeof(prime2));
        int n=0;
        for(int i=1; i<=m; i++) {
            if(prime1[i]>sqrt(U)) break;
            for(ll j=L/prime1[i]; j<=U/prime1[i]; j++) {
                if(prime1[i]*j>=L&&j>1) //要注意的地方
                    v[prime1[i]*j-L]=1;
            }
        }
        if(L==1) v[1-L]=1; //要注意的地方
        for(ll i=L; i<=U; i++) {
            if(!v[i-L]) {
                prime2[++n]=i;
            }
        }

        ll maxn=0;
        ll minn=2147483647;
        ll a,b,c,d;
        for(int i=1; i<=n-1; i++) {
            if(maxn<prime2[i+1]-prime2[i]) {
                maxn=prime2[i+1]-prime2[i];
                a=prime2[i];
                b=prime2[i+1];
            }
            if(minn>prime2[i+1]-prime2[i]) {
                minn=prime2[i+1]-prime2[i];
                c=prime2[i];
                d=prime2[i+1];
            }
        }
        if(n<2)
            printf("There are no adjacent primes.\n");
        else
            printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",c,d,a,b);
    }
    return 0;
}