light_oj 1336 约数和奇偶性

时间：2015-06-03 21:11:18 收藏：0 阅读：459

light_oj 1336 约数和奇偶性

D - 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

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70017#problem/D

题意：求[1,n]中约数和为偶数的数的个数

思路：根据算术基本定理的约数和公式f(n)=(1+p1+p1^2+...+p1^k1)(1+p2+p2^2+...+p2^k2)...(1+pn+pn^3+...+pn^kn);

其中n=(p1^k1)*(p2^k2)*...*(pn^kn);(分解素因数)

由于奇数*奇数还是奇数，奇数*偶数或者偶数相乘是偶数。而素数除了2都是奇数。

f(n)的奇偶性取决于每个因子的奇偶性，只要出现一个因子是偶数时f(n)为偶数。

对每个因子，1+p+p^2+...+p^k的奇偶性，

p为素数，当p是2时，式子为偶数；

当p不是2时，p是奇数数，p^i为奇数，式子总共k+1项，即k+1个奇数的和，k为偶数时式子为奇数。

以此条件反推dfs出所有的f(n)为奇数的n，方法是每次乘以奇素数素数的两倍或者2，得到的n就是f(n)为奇数的n了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<math.h>
#include<cctype>

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=(1<<29);
const double EPS=0.0000000001;
const double Pi=acos(-1.0);

ll n;
vector<ll> odd;
bool isprime[maxn];
vector<int> prime;
const ll M=1000000000010;

void play_prime()
{
    memset(isprime,1,sizeof(isprime));
    isprime[1]=0;
    for(int i=2;i<maxn;i++){
        if(!isprime[i]) continue;
        for(int j=i*2;j<maxn;j+=i){
            isprime[j]=0;
        }
    }
    for(int i=1;i<maxn;i++){
        if(isprime[i]) prime.push_back(i);
    }
}

void dfs(int dep,ll cur)
{
    odd.push_back(cur);
    if(dep>=(int)prime.size()) return;
    for(int i=dep;i<prime.size();i++){
        ll t=prime[i];
        if(t==2){
            if(cur<=M/2) dfs(i,cur*2);
            else return;
        }
        else{
            if(cur<=M/(t*t)) dfs(i,cur*t*t);
            else return;
        }
    }
}

int main()
{
    int T;cin>>T;
    play_prime();
    dfs(0,1);
    sort(odd.begin(),odd.end());
    int tag=1;
    while(T--){
        cin>>n;
        ll ans=upper_bound(odd.begin(),odd.end(),n)-odd.begin();
        printf("Case %d: %lld\n",tag++,n-ans);
    }
    return 0;
}

View Code

原文：http://www.cnblogs.com/--560/p/4550128.html