BZOJ 2818: Gcd-白红宇

BZOJ 2818: Gcd

阅读量：4620 次

发布时间：2019-06-09

本文共 1895 字，大约阅读时间需要 6 分钟。

题目

2818: Gcd

Time Limit: 10 Sec

Memory Limit: 256 MB

Description

给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的

数对(x,y)有多少对.

Input

一个整数N

Output

如题

Sample Input

Sample Output

HINT

hint

对于样例(2,2),(2,4),(3,3),(4,2)

1<=N<=10^7

题解

这题给的内存好极限，我调内存调了好久！【或者说我的方法太low了

求1<i,j<k的gcd(i,j)=1的数量，即为求phi[1~k]的和！

代码

/*Author:WNJXYK*/#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           using namespace std;#define LL long long#define Inf 2147483647#define InfL 10000000000LLinline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}inline void swap(LL &x,LL &y){LL tmp=x;x=y;y=tmp;}inline int remin(int a,int b){if (a
            
             b) return a;return b;}inline LL remin(LL a,LL b){if (a
             
              b) return a;return b;}const int Maxn=10000000;LL n;int prime[Maxn/2+1];bool valid[Maxn+1];int primes;inline void getPrime(){ memset(valid,true,sizeof(valid)); for (int i=2;i<=n;i++){ if (valid[i])prime[++primes]=i; for (int j=1;j<=primes && prime[j]*i<=n;j++){ valid[prime[j]*i]=false; if (i%prime[j]==0) break; } }}/*LL miu[Maxn+10];inline void getMiu(){ for (int i=1;i<=Maxn;i++){ int target=(i==1?1:0); int delta=target-miu[i]; miu[i]=delta; for (int j=i+i;j<=Maxn;j+=i) miu[j]+=delta; }}*/LL phi[Maxn+1];int minDiv[Maxn+1];inline void getPhi(){ for (int i=1;i<=prime[primes];i++) minDiv[i]=i; for (int i=2;i*i<=prime[primes];i++) if (minDiv[i]==i) for (int j=i*i;j<=prime[primes];j+=i) minDiv[j]=i; phi[1]=1; for (LL i=2;i<=prime[primes];i++){ phi[i]=phi[i/minDiv[i]]; if ((i/minDiv[i])%minDiv[i]==0){ phi[i]*=minDiv[i]; }else{ phi[i]*=minDiv[i]-1; } }}LL Sum[Maxn+1];int main(){ scanf("%d",&n); getPrime(); getPhi(); for (int i=1;i<=Maxn;i++)Sum[i]=Sum[i-1]+phi[i]; LL Ans=0; for (int i=1;prime[i]<=n&&i<=primes;i++){ Ans+=Sum[n/prime[i]]*2-1; } printf("%lld\n",Ans); return 0;}