Description

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出\(\Sigma gcd(i, N) (1 \leq i \leq N)\)。

Input

一个整数，为N。

Output

一个整数，为所求的答案。

Sample Input

6

Sample Output

15

Hint

对于60%的数据，\(0<N \leq 2^{16}\)

对于100%的数据，\(0<N \leq 2^{32}\)

Solution

记\(f(k)\)表示\(gcd(m,n)=k\)的\(m(m \leq n)\)的个数，因此\(gcd(m/k,n/k)=1\),于是有\(f(k)=\varphi (n/k)\).

故对于任意\(k|n\),\(k\)对答案的贡献为\(kf(k)=k \varphi (n/k)\),用线筛预处理出\(\sqrt n\)内的质数，然后求欧拉函数求和即可。

时间复杂度\(O(\sqrt n \log n)\)

Code

#include <stdio.h>

#include <math.h>

#define MN (1<<16)

#define R register

#define ll long long

#define file(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);

#define end fclose(stdin);fclose(stdout)

ll n,ans;int phi[MN+5],pr[MN],pn,m;bool b[MN+5];

void pre(){

	phi[1]=1;for (R int i=2; i<=m; ++i){

		if (!b[i]){

			pr[++pn]=i;

			phi[i]=i-1;

		}

		for (R int j=1; j<=pn; ++j){

			if (1ll*i*pr[j]>m) break;

			b[i*pr[j]]=1;

			if (i%pr[j]==0){

				phi[i*pr[j]]=phi[i]*pr[j];

				break;

			}phi[i*pr[j]]=phi[i]*(pr[j]-1);

		}

	}

}

inline ll getphi(ll x){

	R ll q=x,res=x;

	for (R int i=1; i<=pn; ++i)

		if (!(q%pr[i])){

			res=res/pr[i]*phi[pr[i]];

			while((!(q%pr[i]))) q/=pr[i];

		}

	if (q>1) res=res/q*(q-1);return res;

}

int main(){

	scanf("%lld",&n);m=floor(sqrt(n));pre();

	for (R int t=1; t<=m; ++t)

		if (n%t==0){

			ans+=t*getphi(n/t);

			if (t*t<n) ans+=n/t*phi[t];

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

	return 0;

}