某数学题1

P2303 [SDOi2012]Longge的问题

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

输入格式：
一个整数，为N。

输出格式：
一个整数，为所求的答案。

输入样例#1：
6
输出样例#1：
15
说明

对于60%的数据，0<N<=2^16
对于100%的数据，0<N<=2^32

做法

[ans=sum_{i=1}^n (i,n)=sum_{d|n}sum_{i=1}^n[(i,n)=d]d=sum_{d|n}sum_{i=1}^n[(frac{i}{d},frac{n}{d})=1]d ]

[ecause sum_{i=1}^{n}[(a,b)=1]=phi(i) ]

[ herefore ans=sum_{d|n}phi(frac{n}{d})d ]

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;

ll n,ans;

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

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