AcWing 220. 最大公约数
原题链接
简单
作者:
羽笙
,
2019-10-05 10:49:33
,
所有人可见
,
阅读 921
思路和 秦淮岸灯火阑珊 略有(shi fen)相似,这里记录一下
秦同学给出了较为严谨的证明,这里感性的记录下
本题求最大公约数为素数的数对
有gcd(a,b) = d,d是素数
两边同时除d,即gcd(a/d,b/d) = 1;
进而可以发现
对于任何gcd(a,b) = 1
有gcd(ad,bd) = d
也就是对于每个a, 所有与a互质的数乘上一个质数 与 a乘上这个质数 的gcd就是 质数
处理出来所有与i互质的数可以用欧拉函数,欧拉函数是求出比他小的互质的数,因为不关心顺序,计数原理算一下即可
注意需要剔除乘了之后大于n的即可
还有质数和它本身的gcd就是它本身,也要加上
代码