bzoj2818: Gcd

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

4

Sample Output

4

HINT

hint

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

1<=N<=10^7

题解：gcd(x, y) = p   <==> gcd(x/p, y/p) = 1   <==> phi[y/p] if(x/p is smaller)   p is a prime

我们就枚举p好了, x中有x/p个满足为p 的倍数，我们就需要Σ(i < x/p) phi[i] 的前缀和，然后答案*2 -1（*2是交换x和y， -1是因为phi[1]是x == y, 我们这里phi[1] = 1)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int M = 1e7 + 10;
bool vis[M];
int cnt;
int p, phi[M], prime[M];
ll sum[M];
void init(int t){
    phi[1] = 1;
  
    for(int i = 2; i <= t; i++){
        if(!vis[i]) phi[i] = i-1, prime[++cnt] = i;
        for(int j = 1; j <= cnt && i * prime[j] <= t; j++){
            int m = i * prime[j]; vis[m] = 1;
            if(i % prime[j] == 0) {
                phi[m] = phi[i] * prime[j];
                break;
            }
            phi[m] = phi[i] * (prime[j] - 1);
        }
    }
     
    for(int i = 1; i <= t; i++) sum[i] = sum[i-1] + phi[i]*1LL;
}
  
int main(){
    int t;
    ll ans = 0;
    scanf("%d", &t);
    init(t);
    for(int i = 1; i <= cnt; i++)
        ans += 2*sum[t/prime[i]] - 1;//, cout<<sum[t/prime[i]]<<endl;
    printf("%lld", ans);
}