Sigma Function（因子和的性质）

Sigma Function
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Submit Status Practice LightOJ 1336

Description

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.

Sample Input

4

3

10

100

1000

Sample Output

Case 1: 1

Case 2: 5

Case 3: 83

Case 4: 947

题意：求1~n中有多少个数的因子和是偶数

先给出题中公式的推导过程：
n的因子：对于n = x * y，x与y都是a的因子
又有(x^a1 * y^b1) * (x^a2 * y^b2) = x^(a1+a2) * y^(b1+b2)
所以对于n的唯一分解：

n的因子x与y均可以表示为p1^a1 * p2^a2 * … *pk^ak 以及p1^b1 * p2^b2 * … *pk^bk, (a1~ ak, b1~ bk均小于等于对应e1~ ek)
例如设n = 12，n的唯一分解是n = 2^2 * 3，12的因子有1，2，3，4，6，12，他们分别可以表示为：
1 = 2^0 * 3^0
2 = 2^1 * 3^0
3 = 2^0 * 3^1
4 = 2^2 * 3^0
6 = 2^1 * 3^1
12 = 2^2 * 3^1
这样，其因子和s = 1+2+3+4+6+12 = 2^0 * 3^0 + 2^1 * 3^0 + 2^0 * 3^1 + 2^2 * 3^0 + 2^1 * 3^1 + 2^2 * 3^1 = (2^0 + 2^1 + 2^2) * (3^0 + 3^1)，再代入等比数列求和公式得s = (2^3 - 1) / (2 - 1) * (3^2 - 1) / (3 - 1)，题目中的公式，出现了！

解题思路：

对前100个数打表可以看出：当n = 2^x 或 a^2 或2 * a^2时，其因子和为偶数
再对这三个函数打表：
i : 0 1 2 3 4 5 6 7 8 9 …

2^x: 1 2 4 8 16 32 64 128 …

a^2: 0 1 4 9 16 25 36 49 64 …

2a^2: 0 2 8 18 32 50 72 …
可以看出2^x 在 a^2 和2a^2中被全部包含，所以我们只需在1~n中挑选出这些数并统计个数就可以了
但是n的范围很大，肯定不能用for循环一个个去数
我们设1~n中有最大的a使a^2 <= n，由于sqrt(x)单调递增，所以a <= sqrt(n)，即整数1~n中可以写成a^2 的有(int)sqrt(n)个，同理，整数中可以写成2*a^2的有(int)sqrt(n/2)个
所以答案为n - sqrt(n) - sqrt(n/2)

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#define qcin ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int MAXN = 2e5 + 5;
const double eps = 1e-6;
const long long MOD = 1000000007;



int main()
{
    int t;
    scanf("%d", &t);
    int cnt = 0;
    while(t--)
    {
        ll n;
        scanf("%lld", &n);
        ll a = sqrt(n), b = sqrt(n/2);
        printf("Case %d: %lld\n", ++cnt, n-a-b);
    }
    return 0;
}