# 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.

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}为奇数。

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])