## 1336 - Sigma Function

PDF (English)

Statistics

Forum

Time Limit: 2 second(s)

Memory Limit: 32 MB

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

Then we can write,

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 ≤ 1012).

# Output

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

# Output for Sample Input

4

3

10

100

1000

Case 1: 1

Case 2: 5

Case 3: 83

Case 4: 947

### 思路：

• ${ p }_{ i }=2$时，$\sum _{ j=0 }^{ { a }_{ i } }{ { { p }_{ i } }^{ j } }$为奇数
• ${ p }_{ i }\neq 2$时，${ a }_{ i }$ 均为偶数时 $\sum _{ j=0 }^{ { a }_{ i } }{ { { p }_{ i } }^{ j } }$为奇数
因此，我们发现${ a }_{ i }$均为偶数时，有$\sqrt { n } =\sum _{ i=1 }^{ r }{ { { p }_{ i } }^{ \frac { { a }_{ i } }{ 2 } } }$为因子和为奇数的个数，但是缺少了2的幂为奇数的情况，共有$\sqrt { \frac { n }{ 2 } }$种情况，因此最后的答案为$n-\sqrt { n } -\sqrt { \frac { n }{ 2 } }$