【欧拉函数】acwing221

传送门

解法:欧拉函数

俗话说数论上来先打表,打完表智力就正常了

我先打了一张n为50的表
//1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 25 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 50
发现gcd好像有很多重复的数字

gcd为1的就是与50互质的数,个数为\phi{(N)}

gcd为2的个数怎么算?仔细想想,对于每一个gcd(i,N) = d的数对,都存在gcd(i/d , N/d) = 1
也就是说,对于每个数对,各自除以gcd和N都是互质的,那么很明显数对的个数为\phi{(N/d)}

有了以上结论,可以想到,N的所有gcd的可能性就是N的所有约数,对于每个约数,数对的个数为\phi{(N/d)}个,它们的和就是d\phi{(N/d)}

进一步总结,答案就是\sum_{d|N}d\phi{(N/d)}

这个函数是两个积性函数的迪利克雷卷积,所以是个积性函数,有xxxx的性质,可以线筛等等

然而我一看数据范围2^31那比不可能线筛,只能暴力算了。… Read the rest