[牛客小白月赛12]D.月月给华华出题(欧拉函数 + 数学)
题目传送门:D-月月给华华出题_牛客小白月赛12 (nowcoder.com)
如果按照朴素的想法,对于每一个N,用 i 遍历1~N,每一个i又用O(i)的复杂度算出ans[i],复杂度大概是O(N ^ 2 * logN),显然不行,应该找到数字之间的规律.
对于每一个数字x的所有因子d,有可能是x与某个i的最大公因数,于是我们可以改变一个角度,从因子d的角度去思考,如果gcd(i, x) == d,那么就要加上i / d,否则就不加.
再经过一系列的推导,可以得到最后的公式.
关于最后一步欧拉函数性质的解释:如果gcd(d, n) = 1,那么有gcd(