BZOJ2705 SDOI2012 Longge的问题

Description

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

Input

一个整数，为N。

Output

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

Sample Input

Sample Output

HINT

【数据范围】
对于60%的数据，0<N<=2160<N<=216。
对于100%的数据，0<N<=2320<N<=232。

#include<bits/stdc++.h>

using namespace std;

#define LL long long

LL n,m,ans=0;

LL phi(LL t){

    LL tmp=t;

    for(int i=2;i<=m;i++)if(t%i==0){

        tmp=tmp/i*(i-1);

        while(t%i==0)t/=i;

    }

    if(t>1)tmp=tmp/t*(t-1);

    return tmp;

}

int main(){

    cin>>n;m=sqrt(n);

    for(int i=1;i<=m;i++)if(n%i==0){

        ans+=i*phi(n/i);

        ans+=(n/i)*phi(i);

    }

    if(m*m==n)ans-=m*phi(m);

    printf("%lld",ans);

    return 0;

}

巴特西

BZOJ2705 SDOI2012 Longge的问题【欧拉函数】

BZOJ2705 SDOI2012 Longge的问题

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

巴特西

BZOJ2705 SDOI2012 Longge的问题 【欧拉函数】

BZOJ2705 SDOI2012 Longge的问题

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

BZOJ2705 SDOI2012 Longge的问题【欧拉函数】