给定n个正整数ai,请你求出每个数的欧拉函数。
欧拉函数的定义
1 ~ N 中与 N 互质的数的个数被称为欧拉函数,记为ϕ(N)。
若在算数基本定理中,N=pa11pa22…pamm,则:
ϕ(N) = N∗p1−1p1∗p2−1p2∗…∗pm−1pm
输入格式
第一行包含整数n。
接下来n行,每行包含一个正整数ai。
输出格式
输出共n行,每行输出一个正整数ai的欧拉函数。
数据范围
1≤n≤100,
1≤ai≤2∗109
输入样例:
3
3
6
8
输出样例:
2
2
4
字不太好,见笑了
证明方法一(含积性函数证明)
证明方法二
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll k;cin>>k;
while(k--)
{
ll x;
cin>>x;
ll res=x;
for(ll i=2;i<=x/i;i++)
if(x%i==0)
{
while(x%i==0)x/=i;
res=res/i*(i-1); //注意先除再乘 N/pk*(pk-1);
}
if(x>1)res=res/x*(x-1);
cout<<res<<endl;
}
}
“与m互质的数 乘 与n互质的数与mn互质”是错的吧
设m=10,与m互质的数为9
设n=9,与n互质的数为8
但是8x9=72与10x9=90不互质呀,为什么
有大佬可以解答一下吗谢谢
是个数相同
个数相同是欧拉函数的积性函数性质,但他这里是在证明欧拉函数的积性,用的是“数”,不是“个数”,所以证明是错的吧
这证明是错了,我之前就粗略看了,那个评论我删了,抱歉
那可能是我理解错了,抱歉铁子
if(x>1)res=res/x*(x-1);请问为什么会有这个,不是很理解
图借用啦
打卡
感谢
你好,为什么要先乘后除,答案不会呀?
初始式子是(1-1/p),化简后是(p-1)/p,先除后乘是防止爆数据
谢谢大佬
懂了