【数论】【枚举约数】【欧拉函数】bzoj2705 [SDOI2012]Longge的问题

∵∑gcd(i, N)(1<=i <=N)

=k1*s(f1)+k2*s(k2)+...+km*s(km) {ki是N的约数，s(ki)是满足gcd(x,N)=ki(1<=x<=N)的x的个数}

∴gcd(x,N)=ki (1<=x<=N) <=> gcd(x/ki,N/ki)=1 (1<=x/ki<=N/ki)

gcd(x/ki,N/ki)=1 (1<=x/ki<=N/ki) 的x的个数即为φ(N/ki)

∴ans=∑φ(N/ki)*ki

∴O(sqrt(N))枚举约数即可。

 #include<cstdio>

 #include<cmath>

 using namespace std;

 typedef long long ll;

 ll n,ans;

 int phi(ll x)

 {

     ll res=x;

     for(ll i=;i*i<=x;i++)

       if(x%i==)

         {

           res=res/i*(i-);

           while(x%i==) x/=i;

         }

     if(x>) res=res/x*(x-);

     return res;

 }

 int main()

 {

     scanf("%lld",&n);

     for(ll i=;i*i<=n;i++) if(n%i==) ans+=(phi(n/i)*i+phi(i)*(n/i));

     printf("%lld\n",ans);

     return ;

 }

巴特西

【数论】【枚举约数】【欧拉函数】bzoj2705 [SDOI2012]Longge的问题

最新文章

热门文章