[bzoj] 2705 Longge的问题 || 欧拉函数

原题

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

---

(sum^n_{i=1}gcd(i,n))
(=sum_{d|n}sum_{iin [1,n],gcd(i,n)=d}d)
(=sum_{d|n}sum_{iin [1,n/d],gcd(i,n)=1}d)
(=sum_{d|n}d*phi (n/d))

所以(sqrt n)枚举n的约束，(sqrt n)求欧拉函数。
//虽然看起来是(O(sqrt n * sqrt n))的复杂度，但其实能过，因为并不是严格(sqrt n)的

#include<cstdio>
#include<cmath>
typedef long long ll;
using namespace std;
ll n,ans;

ll phi(ll x)
{
    ll t=x;
    for (ll i=2;i<=sqrt(x);i++)
	if (x%i==0)
	{
	    t=t/i*(i-1);
	    while (x%i==0) x/=i;
	}
    if (x>1) t=t/x*(x-1);
    return t;
}

int main()
{
    scanf("%lld",&n);
    for (int i=1;i<=sqrt(n);i++)
	if (n%i==0)
	{
	    ans+=(ll)i*phi(n/i);
	    if (i*i<n) ans+=(ll)(n/i)*phi(i);
	}
    printf("%lld",ans);
    return 0;
}