2182: 不是签到题XD（郑州轻工业大学oj）

Time Limit: 1 Sec Memory Limit: 64 MB

Submit: 105 Solved: 25

SubmitStatusWeb Board

Description

小明是一个贪心的孩子，他天天想着怎么让自己省钱。有一天他去商店买物品，然而他不是普通人，他有一个马基雅把库内的能力，可以只花掉商品价格与他今日幸运数字x的最大公约数的钱就能买走这个商品。那么问题来了，如果他要买价值从1到x元的x个商品，一共要花掉多少钱。

Input

本题有多组测试数据，每组包含一个整数，代表小明今日的幸运数字x，1<=x<=1e11

Output

对于每组输入，请输出他的花费

每组输出占一行

分析

求 ∑ni=1gcd(i,n)

gcd(i,n)=k

∴gcd(i/k,n/k)=1

求 n/k欧拉函数值，即是求有多少个数与n的最大公约数为k，然后将k = 1，2…..n 相加即为所求值

参考代码

LL Euler(LL n){    if(n == 1)        return 1;    LL euler = n;    for(int i = 2;i * i <= n; ++i)    {        if(n % i ==0)        {            euler = euler / i * (i-1);            while(n%i==0)                n /= i;        }    }    if(n != 1)        euler = euler / n *(n-1);    return euler;}int main(void){    std::ios::sync_with_stdio(false);    LL n;    while(cin>>n)    {       LL ans = 0;//       if(n == )       for(LL i = 1;i * i <= n; ++i)       {            if(n % i == 0)            {                ans += i * Euler(n/i);                if(i*i != n)                {                    ans += n/i*Euler(n/(n/i));                }            }       }       cout<
     
      <