本文主要是介绍【欧拉函数】AcWing873. 欧拉函数——欧拉函数的证明与代码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
AcWing873.欧拉函数
证明与题解
#include <iostream>
using namespace std;
int phi(int x)
{
int res = x;
for(int i = 2; i <= x / i; ++i)
{
if(x % i == 0)
{
res = res / i * (i - 1); //先除后乘防止爆int
while(x % i == 0) x /= i;
}
}
if(x > 1) res = res / x * (x - 1);
return res;
}
int main()
{
int n, x;
cin >> n;
while(n -- )
{
cin >> x;
cout << phi(x) << endl;
}
return 0;
}
这篇关于【欧拉函数】AcWing873. 欧拉函数——欧拉函数的证明与代码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!