题目401：因子平方和

永恒的蓝色梦想

                               
登录/注册后可看大图

                               
登录/注册后可看大图

Twilight6

沙发

永恒的蓝色梦想

Twilight6 发表于 2020-5-15 11:56
沙发

这不是每日一题！抢沙发也没用

Twilight6

永恒的蓝色梦想 发表于 2020-5-15 11:57
这不是每日一题！

哈哈 我知道  看到英文 我就开始觉得这帖不简单的

_2_

是不是前 n 个因数……

_2_

sigma2(6)[这里是小写]是 6 的所有因数的平方的和，但是……
万一有(n 的因数的个数 > n )那该怎么处理

永恒的蓝色梦想

_2_ 发表于 2020-5-18 11:51
sigma(6)[这里是小写]是 6 的所有因数的平方的和，但是……
万一有(n 的因数的个数 > n )那该怎么处理

本题从始至终没出现过 sigma

_2_

永恒的蓝色梦想 发表于 2020-5-18 11:53
本题从始至终没出现过 sigma

这个2我没写上……

永恒的蓝色梦想

_2_ 发表于 2020-5-18 11:56
这个2我没写上……

n 的因数的个数 > n

你在逗我

而且这个与本题没什么关系吧

_2_

永恒的蓝色梦想 发表于 2020-5-18 11:58
你在逗我

而且这个与本题没什么关系吧

那好吧

guosl

解题思路：
由于平方函数f(k)是一个积性函数。所以sigma2(n)=(1+f(p1)+f(p1^2)+...+f(p1^k1))...(1+f(pn)+f(pn^2)+...+f(pn^kn))其中n=p1^k1...pn^kn。这样只需分解n成为素因数来计算，再应用MOD一个数的特性即：(a+b) MOD k = ((a MOD k) + (b MOD k)) MOD k和(a x b) MOD k = ((a MOD k) x (b MOD k)) MOD k就把问题要涉及的数大大地减小以至于能计算了。
又1+f(pi)+f(pi^2)+...+f(pi^ki)是一个等比级数的求和。具体计算还可以应用快速幂。
注：积性函数可以参考初等数论的书。