神奇结论:可以分解为两个数的平方和的素数满足$n = 4k+1$或者$n=2$。
[2018.8.27 补充] 该结论是费马平方和定理,表述是:奇质数能表示为两个平方数之和的充分必要条件是该素数被4除余1。
继续阅读
标签:素数筛
Codeforces 920F – SUM and REPLACE
现在有一个数列$a[1…n]$,函数$D(x)$表示$x$的因数个数,有如下操作:
- 给出一个区间$[L, R]$,把区间里的每个数$a_i$替换成$D(a_i)$
- 给出一个区间$[L, R]$,求和