【BZOJ2818】Gcd

首先可以用线性筛找出1-n的所有质数

那么对于每一个质数k,可以让他分别乘上两个互质的数,得到的两个数的gcd就是k

想到互质就是欧拉函数。。

那么再预处理出n以内欧拉函数的前缀和,剩下的就不用多说了。

我个垃圾连欧拉函数都不会求TAT(不过今年论文集里有啊)

说点什么

  Subscribe  
提醒