Sigma Function LightOJ 1336

题目链接:点我

题目

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

---

题意:

求前n个数中因子和为偶数的数的个数

思路:

根据唯一分解定理,我们可以看出每个数都可以表示为p ^ e的形式,那么根据等比数列的前n项和公式,若p为偶数,无论e为奇数还是偶数和都为奇数,因为偶数的任意次方为偶数,那么再加个1,则为奇数,若p为奇数,则若e为奇数,则和为偶数,反之为奇数.
所以和为偶数的情况为p和e都为奇数,其他情况为奇数,又因为奇数的偶数次方和偶数的任意次方都可以写成某个数的平方的形式,所以我们可以得出,当一个数是平方数时,因子和为奇数,这里我们把2单独考虑,因为它是唯一一个偶素数,所以当这个数为平方数的2倍时,因子和也为奇数.
那么我们可以用排除法,减去偶数的情况,剩下的就是奇数了.

代码:

#include<cstdio>
#include<cmath>
using namespace std;

typedef long long LL;

int main()
{
    int t;
    int kase = 0;
    scanf("%d", &t);
    while(t--){
        LL n;
        scanf("%lld", &n);
        LL t1 = (LL)sqrt(n);
        LL t2 = (LL)sqrt(n / 2);
        printf("Case %d: %lld\n", ++kase, n - t1 - t2);
    }
    return 0;
}