久违了！欧拉函数

GCD - HDU 2588 - Virtual Judge (vjudge.net)

题意:

给定n，m,n<=1e9

for(int i=1;i<=n;i++)
{
    if(gcd(i,n)>=m)cnt++;
}

注意到n<=1e9,这个模拟算法是不能通过的

如何优化这个计算过程呢？

若 gcd(i,n)>=m，设d=gcd(i,n),也就是d>=m的时候,cnt++

设i=k1*d,n=k2*d

gcd(i,n)=gcd(k1*d,k2*d)=d*gcd(k1,k2)=d 

也就是：gcd(k1,k2)=1

我们就可以从枚举for(int i=1;i<=n;i++),变为枚举n的因子:for(int i=1;i*i<=n;i++)

此时，若 i是n的因子，则n/i 也是n的因子

即可以O(n)->O(sqrt(n))

转化为，1<=k1<=k2,有多少对gcd(k1,k2)=1

芜湖，这不就是欧拉函数？

注意到若 i*i==n&&i>=m时：i=n/i，这时只加一次

#include<bits/stdc++.h>
int phi(int n)
{
    int m=(int)std::sqrt(n+0.5);
    int ans=n;
    for(int i=2;i<=m;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
int main()
{
    int t;std::cin>>t;
    while(t--)
    {
        int n,m;std::cin>>n>>m;
        int ans=0;
        int d;
        for(d=1;d*d<n;d++)
        {
            if(n%d==0)
            {
                if(d>=m)ans+=phi(n/d);
                if((n/d)>=m)ans+=phi(d);
            }
        }
        if(d*d==n&&d>=m)
        {
            ans+=phi(d);
        }
        std::cout<<ans<<"\n";
    }
    return 0;
}