描述
题解
很有趣的一道题,欧拉函数原来还可以这么玩~~~
既然是1~n与n的公约数,那么肯定是n的因子。
每一个n的因子所对sum产生的增量为:gcd(n, i) = x
(x为这个因子)的个数,也就是gcd(n / x, i / x) = 1
的个数,这时,顺理成章的也就想起了phi(n / x)
了,求欧拉函数的方法多种多样,但是这里不能使用筛法,因为内存会爆掉的,只能单独求解欧拉函数,并且在求n得因子上做一定的优化才行,注意sum必须是long long
类型的哦。
代码
#include <iostream>
#include <cmath>
using namespace std;
/* * 单独求解的本质是公式的应用 */
unsigned euler(unsigned x)
{
unsigned i, res = x; // unsigned == unsigned int
for (i = 2; i < (int)sqrt(x * 1.0) + 1; i++)
{
if (!(x % i))
{
res = res / i * (i - 1);
while (!(x % i))
{
x /= i; // 保证i一定是素数
}
}
}
if (x > 1)
{
res = res / x * (x - 1);
}
return res;
}
int main(int argc, const char * argv[])
{
int N;
cin >> N;
long long sum = 0;
for (int i = 1; i * i <= N; i++)
{
if (N % i == 0)
{
int tmp = N / i;
sum += euler(tmp) * i;
if (i != tmp)
{
sum += euler(i) * tmp;
}
}
}
cout << sum << '\n';
return 0;
}