LightOJ 13361336

http://lightoj.com/volume_showproblem.php?problem=1336

Sigma Function

Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu

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

Output

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

Sample Input

100

1000

Sample Output

Case 1: 1

Case 2: 5

Case 3: 83

Case 4: 947

题目大意：给你一个数n，让你求从1到n中因子和为偶数的数共有多少个，可以用唯一分定理的公式

来找（我这样写过，不过超时）

那么我们可以通过超时的代码将100中不满足的数打出来，如下：

2 3

1 1
4 7
8 15
9 13
16 31
18 39
25 31
32 63
36 91
49 57
50 93
64 127
72 195
81 121
98 171
100 217

发现100中，因子和为奇数的有：

1 2 4 6 9 16 18 25 32 36 49 50 64 72 81 98 100

有没有发现，这些数字有一个规律，他们是 x^2, 2*x, 2*x^2, 只要100中的数满足这三个中的一个，那么，这个数就是不满足的，

总数-不满足的个数 = 满足的个数

我们还可以发现：当x为偶数时2*x和x^2会有重复的部分

当x为奇数时2*x和2*x^2会有重复的部分

那么我们可以将2*x省去，我们求求出x^2的个数和2*x^2的个数，然后用总数减去它们的个数即可

AC代码：

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

int main()
{
    int t, p = 0;
    ll n;
    scanf("%d", &t);
    while(t--)
    {
        p++;
        ll x, y;
        scanf("%lld", &n);
        x = (ll)sqrt(n);//计算n中x^2的个数
        y = (ll)sqrt(1.0 * n / 2);//计算n中2*x^2的个数
        printf("Case %d: %lld
", p, n - x - y);
    }
    return 0;
}

TLE代码（可以用来打表找规律）：

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

int prime[N], k;
bool Isprime[N];

void Prime()
{
    k = 0;
    memset(Isprime, true, sizeof(Isprime));
    Isprime[1] = false;
    for(int i = 2 ; i < N ; i++)
    {
        if(Isprime[i])
        {
            prime[k++] = i;
            for(int j = 2 ; j * i < N ; j++)
                Isprime[j * i] = false;
        }
    }
}

ll solve(ll n)
{
    ll x, y, a;
    ll num = 1;
    for(ll i = 0 ; i < k && prime[i] * prime[i] <= n ; i++)
    {
        x = 0;
        if(n % prime[i] == 0)
          {
              while(n % prime[i] == 0)
              {
                  x++;
                  n /= prime[i];
              }
              x += 1;
              a = 1;
              for(ll j = 1 ; j <= x ; j++)
              a *= prime[i];
              y = a - 1;
               num *= y /(prime[i] - 1);
          }
    }
    if(n > 1)
        num *= ((n * n - 1) / (n - 1));
    return num;
}

int main()
{
    Prime();
    int t, x = 0;
    ll n;
    scanf("%d", &t);
    while(t--)
    {
        x++;
        scanf("%lld", &n);
        ll num = 0;
        for(ll i = 2 ; i <= n ; i++)
        {
            ll m = solve(i);
            if(m % 2 != 0)
               {
                   printf("%lld %lld
", i, m);
                   num++;
               }
        }
        printf("Case %d: %lld
", x, n - 1 - num);
    }
    return 0;
}