数论:欧拉函数的线性求取与应用 – Zechel

例题:GCD最大公约数

这道题中,要我们找到在1~N中找到数对(x,y)来使,gcd(x,y)=d,但是d是一个素数。

了解了欧拉函数之后,我们可以这样假设,对于a,b而言,gcd(a,b)=1,二者互质,那么如果给a,b都乘上一个质数d,那么显然最大公约数就变成了d,即gcd(a×d,b×d)=d。这样,对于一个数 x 而言,根据欧拉函数(在此为phi[ ]数组)的定义,如果有 t个质数d,可以使d×x <= n,phi[ x ]×t 就是x与x小的所有数组合时,形成的合题数对。

由上面的分析,我们要求1~N中的所有数对,就可以反向思考,将N/tmp=k,tmp是某个小于N的质数,那么1~k中所有的phi的值都是直接代表着,当前数和比其小的数组合存在的合题数对的数量。然后

for(int i=1;i<=k;i++)
{
      sum=sum+phi[i];
}

这样,sum就是gcd(x,y)=tmp的数对(x,y)的总数量。

这样,我们只需要先求出N以内的所有质数,然后枚举一遍,进行上诉操作,最后加在一起就可以得到结果。本题需要注意的是,(x,y)和(y,x)是两个数对,且x可以等于y(当x=y,且为质数时合题),所以还需要最后处理一下结果。

关于求得phi[ i ]数组的值,只需要利用欧拉函数的递推式,可以利用线性筛素数的方法来求得,几乎在原算法上没有改动,既能算出欧拉函数值,还可以求得此时的质数集。利用的是所有素数只出现一次,并且素数先出现,可以直接确定质数的欧拉函数值,再筛合数,这样就给递推提供了条件。

int prime[maxn];
int check[maxn];
long long phi[maxn];
int tot=0;
void get_ola(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!check[i])
        {
            prime[tot]=i;
            tot++;
            phi[i]=i-1;    //质数的欧拉函数值等于其值减一
        }
        for(int j=0;j<tot&&prime[j]*i<=n;j++)
        {
            check[i*prime[j]]=1;
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);//递推式
            if(i%prime[j])break;
        }
    }
}

完整代码如下:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#define maxn 10000005
using namespace std;
int prime[maxn];
int check[maxn];
long long phi[maxn];
long long sum[maxn];
int tot=0;
void get_ola(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!check[i])
        {
            prime[tot]=i;
            tot++;
            phi[i]=i-1;
        }
        for(int j=0;j<tot&&prime[j]*i<=n;j++)
        {
            check[i*prime[j]]=1;
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
            if(i%prime[j])break;
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    get_ola(n);
    long long ans=0;
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+phi[i];
    for(int i=0;i<tot;i++)
    {
        int now=n/prime[i];
        ans+=2*sum[now];
    }
    ans+=tot;
    cout<<ans;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

川公网安备 51130202000337号