gcd
- gcd(n+m,n)=gcd(n,m),gcd(n,m)=gcd(m,nmodm)
看似简单的性质配合欧拉函数的定义，有
- 若正整数 a+b=n，则 (a,b) 可以形成 φ(n) 个互质对
- 若正整数 a+b=n，则 满足 gcd(a,b)=k 的有序数对有 φ(n/k) 个
注：将 gcd(a,b)=k 转换为 gcd(a+b,b)=gcd(n,b)=k 即证
3 评论
x
绊缘
,
2023-08-03 23:03:13
,
所有人可见
,
阅读 505
看似简单的性质配合欧拉函数的定义，有
- 若正整数 a+b=n，则 (a,b) 可以形成 φ(n) 个互质对
- 若正整数 a+b=n，则 满足 gcd(a,b)=k 的有序数对有 φ(n/k) 个
注：将 gcd(a,b)=k 转换为 gcd(a+b,b)=gcd(n,b)=k 即证
想了好久这道题，准备启动vscode开始码，然后发现我已经写过了（
对的，当时写的时候没思路，看一下这个鬼题目到底代码复不复杂，然后看到了你写的线性筛欧拉函数
感觉调和级数写法的欧拉函数更简便(●’◡’●)