【数论】【枚举约数】【欧拉函数】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))枚举约数即可。

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 typedef long long ll;
 5 ll n,ans;
 6 int phi(ll x)
 7 {
 8     ll res=x;
 9     for(ll i=2;i*i<=x;i++)
10       if(x%i==0)
11         {
12           res=res/i*(i-1);
13           while(x%i==0) x/=i;
14         }
15     if(x>1) res=res/x*(x-1);
16     return res;
17 }
18 int main()
19 {
20     scanf("%lld",&n);
21     for(ll i=1;i*i<=n;i++) if(n%i==0) ans+=(phi(n/i)*i+phi(i)*(n/i));
22     printf("%lld
",ans);
23     return 0;
24 }