51nod 1040 最大公约数的和 欧拉函数

1040 最大公约数之和

题目来源： rihkddd

基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题

 收藏

 关注

给出一个n，求1-n这n个数，同n的最大公约数的和。比如：n = 6

1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6，加在一起 = 15

 

Input

1个数N(N <= 10^9)

Output

公约数之和

Input示例

6

Output示例

15
思路：欧拉函数（可能好久没写欧拉，有点忘了）；

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 1000000009

#define inf 999999999

#define esp 0.00000000001

//#pragma comment(linker, "/STACK:102400000,102400000")

int scan()

{

    int res =  , ch ;

    while( !( ( ch = getchar() ) >= '' && ch <= '' ) )

    {

        if( ch == EOF ) return  <<  ;

    }

    res = ch - '' ;

    while( ( ch = getchar() ) >= '' && ch <= '' )

        res = res *  + ( ch - '' ) ;

    return res ;

}

int phi(int n)

{

    int i,rea=n;

    for(i=;i*i<=n;i++)

    {

        if(n%i==)

        {

            rea=rea-rea/i;

            while(n%i==)  n/=i;

        }

    }

    if(n>)

        rea=rea-rea/n;

    return rea;

}

int main()

{

    int x,y,z,i,t;

    while(~scanf("%d",&x))

    {

        ll ans=;

        for(i=;i*i<=x;i++)

        {

            if(x%i==)

            {

                if(i*i!=x)

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

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

            }

        }

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

    }

    return ;

}