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

n = p 1 e 1 × p 2 e 2 × . . . × p k e k n=p_{1}^{e_{1}}\times p_{2}^{e_{2}}\times ...\times p_{k}^{e_{k}} n=p1e1​​×p2e2​​×...×pkek​​

Then we can write,

σ ( n ) = p 1 e 1 + 1 − 1 p 1 − 1 × p 2 e 2 + 1 − 1 p 2 − 1 × . . . × p k e k + 1 − 1 p k − 1 \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} σ(n)=p1​−1p1e1​+1​−1​×p2​−1p2e2​+1​−1​×...×pk​−1pkek​+1​−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 ≤ 1 0 12 ) n (1 ≤ n ≤ 10^{12}) 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 1 e 1 + 1 − 1 p 1 − 1 × p 2 e 2 + 1 − 1 p 2 − 1 × . . . × p k e k + 1 − 1 p k − 1 \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} ∵σ(n)=p1​−1p1e1​+1​−1​×p2​−1p2e2​+1​−1​×...×pk​−1pkek​+1​−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 p=2 p=2时， p e + 1 − 1 p − 1 \frac{p^{e+1}-1}{p-1} p−1pe+1−1​一定为奇数
  • 当 p ≠ 2 p\ne2 p̸​=2时( p p p一定为奇数，因为素数中只有 2 2 2是偶数)，当且仅当 e e e为偶数时 p e + 1 − 1 p − 1 \frac{p^{e+1}-1}{p-1} p−1pe+1−1​为奇数

设 k = e + 1 k=e+1 k=e+1则 p e + 1 − 1 p − 1 = p k − 1 p − 1 \frac{p^{e+1}-1}{p-1}=\frac{p^{k}-1}{p-1} p−1pe+1−1​=p−1pk−1​，若 k k k为偶数( e e e为奇数)则可化简为 ( p k 2 − 1 ) × ( p k 2 + 1 ) p − 1 \frac{(p^{\frac{k}{2}}-1)\times (p^{\frac{k}{2}}+1)}{p-1} p−1(p2k​−1)×(p2k​+1)​， ∵ p k 2 \because p^{\frac{k}{2}} ∵p2k​为奇数， ∴ p k 2 − 1 \therefore p^{\frac{k}{2}}-1 ∴p2k​−1和 p k 2 + 1 p^{\frac{k}{2}}+1 p2k​+1都为偶数， ∴ ( p k 2 − 1 ) × ( p k 2 + 1 ) p − 1 = ( p k 2 − 1 ) × p k 2 + 1 p − 1 = p k 2 − 1 p − 1 × ( p 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) ∴p−1(p2k​−1)×(p2k​+1)​=(p2k​−1)×p−1p2k​+1​=p−1p2k​−1​×(p2k​+1)，无论 p k 2 + 1 p − 1 \frac{p^{\frac{k}{2}}+1}{p-1} p−1p2k​+1​或 p k 2 − 1 p − 1 \frac{p^{\frac{k}{2}}-1}{p-1} p−1p2k​−1​是奇数还是偶数当它乘上一个偶数 p k 2 − 1 p^{\frac{k}{2}}-1 p2k​−1或 p k 2 + 1 p^{\frac{k}{2}}+1 p2k​+1之后整体一定是一个偶数，若 k k k为奇数则分子不可拆分

∴ \therefore ∴当且仅当 e e e为偶数时 p e + 1 − 1 p − 1 \frac{p^{e+1}-1}{p-1} p−1pe+1−1​为奇数。

即对于任意一个数 x x x， σ ( x 2 ) \sigma(x^{2}) σ(x2)和 σ ( 2 y × x 2 ) \sigma(2^{y}\times x^{2}) σ(2y×x2)一定是奇数(因为当 p = 2 p=2 p=2时， p e + 1 − 1 p − 1 \frac{p^{e+1}-1}{p-1} p−1pe+1−1​一定为奇数)。

对于题目要求出 1 → n 1\rightarrow n 1→n中 σ ( n ) \sigma(n) σ(n)为偶数的个数，先求出 1 → n 1\rightarrow n 1→n中 σ ( n ) \sigma(n) σ(n)为奇数的个数，分两种情况

  1. 求出所有 σ ( x 2 ) ( x 2 ∈ [ 1 , n ] ) \sigma(x^{2})(x^{2}\in [1,n]) σ(x2)(x2∈[1,n])数量，那么对于所有 i ∈ [ 1 , ⌊ n ⌋ ] i\in[1,\lfloor\sqrt{n}\rfloor] i∈[1,⌊n ​⌋]，都有 i 2 ∈ [ 1 , n ] i^{2}\in[1,n] i2∈[1,n]，数量为 ⌊ n ⌋ \lfloor\sqrt{n}\rfloor ⌊n ​⌋
  2. 求出所有 σ ( 2 × x 2 ) ( ( 2 × x 2 ) ∈ [ 1 , n ] ) \sigma(2\times x^{2})((2\times x^{2})\in [1,n]) σ(2×x2)((2×x2)∈[1,n])数量，那么对于所有 i ∈ [ 1 , ⌊ n 2 ⌋ ] i\in[1,\lfloor\sqrt{\frac{n}{2}}\rfloor] i∈[1,⌊2n​ ​⌋]，都有 ( 2 × i 2 ) ∈ [ 1 , n ] (2\times i^{2})\in[1,n] (2×i2)∈[1,n]，数量为 ⌊ n 2 ⌋ \lfloor\sqrt{\frac{n}{2}}\rfloor ⌊2n​ ​⌋

σ ( 2 y × x 2 ) \sigma(2^{y}\times x^{2}) σ(2y×x2)中当 y > 1 y>1 y>1时 σ ( 2 y × x 2 ) \sigma(2^{y}\times x^{2}) σ(2y×x2)可以被分解为 σ ( z 2 ) ( z ∈ [ 1 , x ] ) \sigma(z^{2})(z\in[1,x]) σ(z2)(z∈[1,x])或 σ ( 2 × z 2 ) ( z ∈ [ 1 , n ] ) \sigma(2\times z^{2})(z\in[1,n]) σ(2×z2)(z∈[1,n])

例如 σ ( 2 2 × x 2 ) = σ ( ( 2 × x ) 2 ) \sigma(2^{2}\times x^{2})=\sigma((2\times x)^{2}) σ(22×x2)=σ((2×x)2)， σ ( 2 3 × x 2 ) = σ ( 2 × 2 2 × x 2 ) = σ ( 2 × ( 2 × x ) 2 ) \sigma(2^{3}\times x^{2})=\sigma(2\times 2^{2}\times x^{2})=\sigma(2\times (2\times x)^{2}) σ(23×x2)=σ(2×22×x2)=σ(2×(2×x)2)

所以无需重复计算。

最后把两种数量相加即为 1 → n 1\rightarrow n 1→n中 σ ( n ) \sigma(n) σ(n)为奇数的个数，用 n n n减去 1 → n 1\rightarrow n 1→n中 σ ( n ) \sigma(n) σ(n)为奇数的个数即为 1 → n 1\rightarrow n 1→n中 σ ( n ) \sigma(n) σ(n)为偶数的个数。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
	char c;
	int sgn;
	if (c = getchar(), c == EOF) {
		return 0;
	}
	while (c != '-' && (c < '0' || c > '9')) {
		c = getchar();
	}
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0' && c <= '9') {
		ret = ret * 10 + (c - '0');
	}
	ret *= sgn;
	return 1;
}
template <class T>
inline void out(T x) {
	if (x > 9) {
		out(x / 10);
	}
	putchar(x % 10 + '0');
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	ll t;
	read(t);
	for (ll Case = 1, n; Case <= t; ++Case) {
		read(n);
		printf("Case %lld: %lld\n", Case, n - ll(sqrt(n)) - ll(sqrt(n / 2)));
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}