永恒的蓝色梦想 发表于 2020-5-15 11:55:39

题目401：因子平方和

https://s1.ax1x.com/2020/05/15/Yr0WV0.png
https://s1.ax1x.com/2020/05/15/Yr02bq.png

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

沙发{:10_279:}

永恒的蓝色梦想 发表于 2020-5-15 11:57:49

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

这不是每日一题！抢沙发也没用{:10_277:}

Twilight6 发表于 2020-5-15 11:58:54

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

哈哈 我知道{:10_277:}看到英文 我就开始觉得这帖不简单的{:10_334:}

_2_ 发表于 2020-5-18 11:47:12

是不是前 n 个因数……

_2_ 发表于 2020-5-18 11:51:44

本帖最后由 _2_ 于 2020-5-18 11:56 编辑

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

永恒的蓝色梦想 发表于 2020-5-18 11:53:09

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

本题从始至终没出现过 sigma

_2_ 发表于 2020-5-18 11:56:28

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

这个2我没写上……

永恒的蓝色梦想 发表于 2020-5-18 11:58:38

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

n 的因数的个数 > n 你在逗我

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

_2_ 发表于 2020-5-18 12:18:49

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

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

那好吧

guosl 发表于 2020-5-22 10:00:04

本帖最后由 guosl 于 2020-5-22 13:39 编辑

解题思路：
由于平方函数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)是一个等比级数的求和。具体计算还可以应用快速幂。
注：积性函数可以参考初等数论的书。
页: [1]
查看完整版本: 题目401：因子平方和