Sigma Function Input

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 ≤ 10¹²).

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

Sample Input

4

3

10

100

1000

Case 1: 1

Case 2: 5

Case 3: 83

Case 4: 947

题目扩展：

题意：

求1—n中，有多少个数的因子和是偶数。

题解：

打表找规律。

素因子分解打表计算前n项和判断奇数偶数可以发现如下规律：

只要是2^x,x^2,2*x^2...只有这种数的因子和是奇数。所以，我们直接去重即可。
但是这些直接去重我们会发现减去的这些值有重复的，所以我们要判断下。

i(代表x||a):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 ......

2*a^2:0 2 8 18 32 50 72 ......

我们可以发现2^x里面有的数，x^2和2*x^2里面都有。

加下划线的字一一对应，加粗的字一一对应。

①2^x和x^2, 当x为偶数时二者出现重复。
②2^x和2*x^2，当x为奇数时，二者出现重复。

所以不需要考虑2^x的个数，直接用n减去x^2和2*x^2的个数就是我们要的结果。

易知：x^2的个数=sqrt(n)，2*x^2的个数=sqrt(n/2)。

那么为什么会是这样呢？给出推导过程：

n=p1^e1*p2^e2...,则f(n)=(p1^(e1+1)-1)/(p1-1))*(p2^(e2+1)-1)/(p2-1))....
且(p1^(e1+1)-1）/(p1-1))=p1^0+p1^1......+p1^e1;
要使得f(n)为奇数，则(p1^(e1+1)-1)/(p1-1)到(pn^(en+1)-1)/(pn-1)都要为奇数;

因为奇数*奇数=奇数，奇数*偶数=偶数;

1)当p=2时，2^(e+1)-1,一定为奇数;
2)当p!=2时，则p为奇数(因为p是素因子)，则当e为偶数时(p^(e+1)-1)/(p-1)为奇数。Sn=(p^(e+1)-1)/(p-1)，相当于首项为1，公比为p的数列求和，p为奇素数，当e为偶数时，为奇数项奇数求和,结果必为奇数。

代码如下：

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define ll long long
int main()
{
    int t,cc=1;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        printf("Case %d: %lld\n",cc++,n-(int)sqrt(n)-(int)sqrt(n/2));
    }

}

转自：https://www.cnblogs.com/Ritchie/p/5299970.html