【BZOJ-2818】Gcd 线性筛

2818: Gcd

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 3347  Solved: 1479
[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

Source

湖北省队互测

Solution

首先，所求的是$sum_{i=1}^{N}sum_{j=1}^{N}left [ gcdleft ( i,j ight )= p ight ]$

那么转化一下就可以得到$sum_{i=1}^{N}sum_{j=1}^{N}left [ gcdleft ( frac{i}{p},frac{j}{p} ight )= 1 ight ]$

那么我们定义$fleft [ i ight ]$表示1～i中满足$gcdleft ( x,y ight )= 1$的个数

那么很显然可以得到 $fleft [ i ight ]= 1+2*sum_{j=1}^{i}varphi left ( j ight )$

上述式子很好想，考虑$varphi$的定义，以及$gcdleft ( a,b ight )= gcdleft ( b,a ight )$再考虑$left ( 1,1 ight )$的情况

所以很显然，结果就是$sum_{i=1}^{cnt}fleft [ frac{n}{prime[i]]} ight ]$

值得注意的是，不要计算重复，具体的看代码即可

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 10000010
int prime[maxn],cnt;long long phi[maxn],f[maxn];
bool flag[maxn];
void prework(int n)
{
    phi[1]=1; flag[1]=1; f[1]=1;
    for (int i=2; i<=n; i++)
        {
            if (!flag[i]) prime[++cnt]=i,phi[i]=i-1;
            for (int j=1; j<=cnt&&i*prime[j]<=n; j++)
                {
                    flag[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=3; i<=n; i++) phi[i]+=phi[i-1];
    for (int i=2; i<=n; i++) f[i]=1+2*phi[i];
}
void work(int n)
{
    long long ans=0;
    for (int i=1; i<=cnt; i++)
        if (n/prime[i]) ans+=f[n/prime[i]];
    printf("%lld
",ans);
}
int main()
{
    int n;
    scanf("%d",&n);
    prework(n+1); work(n);
    return 0;
}

简单数论！一点都不慌