2818: Gcd

2818: Gcd

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 4488  Solved: 1984
[Submit][Status][Discuss]

Description

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

Input

一个整数N

Output

如题

Sample Input

4

Sample Output

4

HINT

hint

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

1<=N<=10^7

【题解】：

gcd(a,b)=p 则 gcd(a/p,b/p)=1;

设 a<=b 则gcd(a,b)=phi[b]（与b互质的个数）

所以只需要枚举每一个素数，每一个数（这里可以用n的前缀和来维护，记为sum[n]）求解出ans=Σf[n/prime[i]]*2-1(考虑a>b，并减去(1,1)之类的值)

【代码】：

1

#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e7+10;
bool check[N];
int n,tot,prime[N/3];
int phi[N];
ll ans,f[N];
void sieve(){
    f[1]=phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!check[i]) prime[++tot]=i,phi[i]=i-1;
        for(int j=1;j<=tot&&i*prime[j]<=n;j++){
            check[i*prime[j]]=1;
            if(!(i%prime[j])){phi[i*prime[j]]=phi[i]*prime[j];break;}
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=2;i<=n;i++) f[i]=f[i-1]+(phi[i]<<1);
}
int main(){
    scanf("%d",&n);
    sieve();
    for(int i=1;i<=tot;i++) ans+=f[n/prime[i]];
    printf("%lld
",ans);
//  printf("
%lf.sec
",(double)clock()/CLOCKS_PER_SEC);
    return 0;
}

 2

//#include<ctime>
#include<cstdio>
#include<iostream>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
typedef long long ll;
const int M=1e7+5;
int n,m,T;ll ans,sum[M];
int tot,prime[M/3],mu[M];bool check[M];
void sieve(){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!check[i]) prime[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&i*prime[j]<=n;j++){
            check[i*prime[j]]=1;
            if(!(i%prime[j])){mu[i*prime[j]]=0;break;}
            else mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i];
}
inline ll s2(int x){return 1LL*x*x;}
inline ll solve(int n){
    ll ans=0;
    for(int i=1,pos;i<=n;i=pos+1){
        pos=n/(n/i);
        ans+=s2(n/i)*(sum[pos]-sum[i-1]);
    }
    return ans;
}
int main(){
    scanf("%d",&n);sieve();
    for(int i=1;i<=tot;i++) ans+=solve(n/prime[i]);
    printf(LL"
",ans);
//    printf("
%.3lf.sec",(double)clock()/CLOCKS_PER_SEC);
    return 0;
}