欧拉函数——最大公约数（gcd+筛质数+欧拉函数）

传送门：220. 最大公约数 - AcWing题库

思路：

题目要求的gcd（x,y）=p;(这里设p为质数)，可以得到 gcd(x/p,y/p)=1; 

题目转化为在1~N/p中找到a，b满足gcd（a,b）=1;因为最后要转化为gcd(a*p,b*p)=p;

到这里题目转化成为求1~N的每个数的欧拉函数。以及求出N的所有质因数p。

第一步：用埃氏筛法求1~N的欧拉函数以及N的质因数（N有可能是质数，所以1~N都要求欧拉函数）

第二步：累加欧拉前缀值sum[i]，优化计算。

第三步：对每一个质数pi，求出N/pi , 累加sum[N/pi]*2+1。 

注意：题目的数对是无序的，所以答案要乘2，同时，当x==y==p时，这个数对（x,y）也成立，所以要加1.

埃氏筛法代码：

#include
#include
#include
#include
#include
#include
using namespace std;
typedef pair<int,int>PII;
typedef long long ll;
const int N=1e7+10,M=1e7+10;
int phi[N],cnt;
int primes[N];
int n;
ll sum[N];
void get()
{
    for(int i=2;i<=n;i++) phi[i]=i;
    for(int i=2;i<=n;i++)
    {
        if(phi[i]==i)
        {
            primes[++cnt]=i;
            for(int j=i;j<=n;j+=i)
                phi[j]=phi[j]/i*(i-1);
        }
    }
}
int main()
{
    scanf("%d",&n);
    get();
    ll ans=0;
    for(int i=2;i<=n;i++)
        sum[i]+=sum[i-1]+phi[i];
    for(int i=1;i<=cnt;i++)
    {
        int t=n/primes[i];
        ans+=sum[t]*2+1;
    }
    cout<
    return 0;
}

线筛法代码：

思路：

由欧拉函数的两个性质。

1.设p是质数，若n%p==0且n%（p^2）==0,则phi[n]=phi[n/p]*p;

2.设p是质数，若n%p==0但n%（p^2）！=0,则phi[n]=phi[n/p]*(p-1);

线筛法中，每个合数都只会被最小的质因数筛一次，此时可以做上面的判断？？？

区别：这里phi[i]初始化为i-1，因为这里是采用递推求值，埃氏筛是根据公式求值

#include
#include
#include
#include
#include
#include
using namespace std;
typedef pair<int,int>PII;
typedef long long ll;
const int N=1e7+10,M=1e7+10;
int phi[N],cnt;
int primes[N];
bool st[N];
int n;
ll sum[N];
void get()
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;primes[j]<=n/i;j++)
        {
            int t=primes[j]*i;
            st[t]=true;
            if(i%primes[j]==0)
            {
                phi[t]=phi[i]*primes[j];
                break;
            }else{
            phi[t]=phi[i]*(primes[j]-1);
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    get();
    ll ans=0;
    for(int i=2;i<=n;i++)
        sum[i]+=sum[i-1]+phi[i];
    for(int i=1;i<=cnt;i++)
    {
        int t=n/primes[i];
        ans+=sum[t]*2+1;
    }
    cout<
    return 0;
}