Sigma Function（唯一分解定理）

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 n = p1^e1 * p2^e2 * … * pk^ek
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 ≤ 10¹²).

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之间的数因子和是偶数的个数

解题思路：

由图可知，此为等比数列求和公式，即第i个乘数为pi⁰+pi¹+pi²+…+pi^e
我们可以求出σ(n)为奇数的个数ans，在用n - ans得出答案
若要σ(n)为奇数，则需要其每个乘数都为奇数，而若要其乘数为奇数，则要e为偶数（因为除了2以外的素数都为奇数，而奇数的x次方依旧为奇数,但若pi为2，pi⁰+pi¹+pi²+…+pi^e恒为奇数），则可分为两种情况讨论
1.σ(n)中所有ei都为偶数，则n必为某个数的平方，而1~n中有sqrt(n)个平方数
2.σ(n)中2的指数为奇数，其余的ei为偶数，则n必为某个平方数的两倍，1~n中有sqrt(n/2)个平方数的两倍

ac代码

#include <math.h>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
using namespace std;int main() {int t;scanf("%d", &t);ll n, ans;for (int k = 1; k <= t; k++) {scanf("%lld", &n);ans = n;ans -= (int)sqrt(n);ans -= (int)sqrt(double(n / 2));printf("Case %d: %lld\n", k, ans);    }return 0;
}