LightOJ 1336 Sigma Function

  • 2018-08-08
  • 19
  • 0

题目:

Sigma function is an interesting function in Number Theory. It is denoted by the Greek letter Sigma (σ). This function actually denotes the sum of all divisors of a number. For example σ(24) = 1+2+3+4+6+8+12+24=60. Sigma of small numbers is easy to find but for large numbers it is very difficult to find in a straight forward way. But mathematicians have discovered a formula to find sigma. If the prime power decomposition of an integer is

n=p_{1}^{e_{1}}\times p_{2}^{e_{2}}\times …\times p_{k}^{e_{k}}

Then we can write,

\sigma(n)=\frac{p_{1}^{e_{1}+1}-1}{p_{1}-1}\times \frac{p_{2}^{e_{2}+1}-1}{p_{2}-1}\times …\times \frac{p_{k}^{e_{k}+1}-1}{p_{k}-1}

For some n the value of σ(n) is odd and for others it is even. Given a value n, you will have to find how many integers from 1 to n have even value of σ.

Input:

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 10^{12}).

Output:

For each case, print the case number and the result.

Sample Input:

4
3
10
100
1000

Sample Output:

Case 1: 1
Case 2: 5
Case 3: 83
Case 4: 947

题目链接

\because \sigma(n)=\frac{p_{1}^{e_{1}+1}-1}{p_{1}-1}\times \frac{p_{2}^{e_{2}+1}-1}{p_{2}-1}\times …\times \frac{p_{k}^{e_{k}+1}-1}{p_{k}-1},奇数\times奇数=奇数,偶数\times偶数=偶数,奇数\times偶数=偶数

\therefore \sigma 中任意一项\frac{p^{e+1}-1}{p-1}为偶数,则\sigma为偶数,只有\sigma中所有\frac{p^{e+1}-1}{p-1}都是奇数\sigma才是奇数

  • p=2时,\frac{p^{e+1}-1}{p-1}一定为奇数
  • p\ne2时(p一定为奇数,因为素数中只有2是偶数),当且仅当e为偶数时\frac{p^{e+1}-1}{p-1}为奇数

k=e+1\frac{p^{e+1}-1}{p-1}=\frac{p^{k}-1}{p-1},若k为偶数(e为奇数)则可化简为\frac{(p^{\frac{k}{2}}-1)\times (p^{\frac{k}{2}}+1)}{p-1}\because p^{\frac{k}{2}}为奇数,\therefore p^{\frac{k}{2}}-1p^{\frac{k}{2}}+1都为偶数,\therefore \frac{(p^{\frac{k}{2}}-1)\times (p^{\frac{k}{2}}+1)}{p-1}=(p^{\frac{k}{2}}-1)\times \frac{p^{\frac{k}{2}}+1}{p-1}=\frac{p^{\frac{k}{2}}-1}{p-1}\times (p^{\frac{k}{2}}+1),无论\frac{p^{\frac{k}{2}}+1}{p-1}\frac{p^{\frac{k}{2}}-1}{p-1}是奇数还是偶数当它乘上一个偶数p^{\frac{k}{2}}-1p^{\frac{k}{2}}+1之后整体一定是一个偶数,若k为奇数则分子不可拆分

\therefore当且仅当e为偶数时\frac{p^{e+1}-1}{p-1}为奇数。

即对于任意一个数x\sigma(x^{2})\sigma(2^{y}\times x^{2})一定是奇数(因为当p=2时,\frac{p^{e+1}-1}{p-1}一定为奇数)。

对于题目要求出1\rightarrow n\sigma(n)为偶数的个数,先求出1\rightarrow n\sigma(n)为奇数的个数,分两种情况

  1. 求出所有\sigma(x^{2})(x^{2}\in [1,n])数量,那么对于所有i\in[1,\lfloor\sqrt{n}\rfloor],都有i^{2}\in[1,n],数量为\lfloor\sqrt{n}\rfloor
  2. 求出所有\sigma(2\times x^{2})((2\times x^{2})\in [1,n])数量,那么对于所有i\in[1,\lfloor\sqrt{\frac{n}{2}}\rfloor],都有(2\times i^{2})\in[1,n],数量为\lfloor\sqrt{\frac{n}{2}}\rfloor

\sigma(2^{y}\times x^{2})中当y>1\sigma(2^{y}\times x^{2})可以被分解为\sigma(z^{2})(z\in[1,x])\sigma(2\times z^{2})(z\in[1,n])

例如\sigma(2^{2}\times x^{2})=\sigma((2\times x)^{2})\sigma(2^{3}\times x^{2})=\sigma(2\times 2^{2}\times x^{2})=\sigma(2\times (2\times x)^{2})

所以无需重复计算。

最后把两种数量相加即为1\rightarrow n\sigma(n)为奇数的个数,用n减去1\rightarrow n\sigma(n)为奇数的个数即为1\rightarrow n\sigma(n)为偶数的个数。

AC代码:

评论

还没有任何评论,你来说两句吧