题目描述

给定整数N，求$ \sum_{ i = 1 } ^ n gcd(i,n)$。

输入格式 Input Format

一个整数$N。N<=2 ^ {32} $

输出格式 Output Format

输出一个整数，表示满足条件的数对数量.

输入：

6

输出：

15

---

想法

由题意可知，输入一个n，输出1~n所有数与n的最大公约数的个数和。
乍一看很难，实际上并不是，设k=gcd(i,n)，则 $ \frac {i}{k} $ 与 $ \frac {n}{k} $互质，
我们可以通过枚举k来得到所有与n的最大公约数为k的数
——也就是除以k之后与 $ \frac {n}{k} $ 互质，也就是说$ \frac {n}{k}$的欧拉函数值即为与n最大公约数为k的数的数目。

之后用sum来累加$ k * \phi ( \frac {n}{k} ) $就是答案。

PS：如果首先预处理的话，则会爆空间，所以说只能找到一个k再找$ \frac{n}{k} $的欧拉函数值（蜜汁不超时）。

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<utility>
using namespace std;
long long n;
long long phi(long long x)
{
	int m=sqrt((double)x);
    long long k=x;
    for(long long i=2;i<=m;i++)
	{
        if(x%i==0)
		{
            k=k/i*(i-1);
            while(x%i==0)x/=i;
        }
    }
    if(x>1)k=k/x*(x-1);
    return k;
}
long long sum=0;
int main()
{
	cin>>n;
	for(int i=1;i*i<=n;i++)
	{
		if(n%i==0)
		{
			sum+=i*phi(n/i);
			if(i*i<n)
			sum+=(n/i)*phi(i);
			//cout<<i<<' '<<n/i<<':'<<phi[i]<<' '<<phi[n/i]<<"    "<<sum<<endl;
		}
	}
	cout<<sum<<endl;
	return 0;
}