【bzoj2705】[SDOI2012]Longge的问题

2015.05.27 20:33 Wed | 20次阅读 | 旧日oi | 固定链接 | 源码

Description

Longge的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。现在问题来了:给定一个整数N,你需要求出∑gcd(i, N)(1<=i <=N)。
题解
考虑枚举gcd(i,N) 的值,对于gcd(i,N)=k的i,有gcd(i/k,n/k)=1,所以只要求出所有的Φ(n/k)即可,我能打数学符号了!!!

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n,ans;
ll phi(ll x)
{
    ll ret=x;
    for(ll i=2;i*i<=x;i++)
    if(x%i==0)
    {
        ret=ret/i*(i-1);
        while(x%i==0) x/=i;
    }
    if(x>1) ret=ret/x*(x-1);
    return ret;
}
int main()
{
    cin>>n;
    for(ll i=1;i*i<=n;i++)
    if(n%i==0)
    {
        ans+=i*phi(n/i);
        if(i*i<n) ans+=(n/i)*phi(i);
    }
    cout<<ans<<endl;
}```