LightOJ Sigma Function 1336【打表+规律】

题意：

求1—N中，有多少数的 σ(a) 值是偶数。

解题思路：

开始就根据公式，发现只要乘积中出现一个偶数即可。然后各种打表算啊。。。

结果发现N=10000的时候程序出结果都很慢。。。这样交上去肯定TLE。

然后打表，打出100之内所有符合条件的数，然后找规律。。。。

发现只要是2^x,x^2,2*x^2...只有这种数没有出现过。所以，我们直接去重即可。

但是这些直接去重我们会发现减去的这些值有重复的，所以我们要判断下。

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

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

所以直接用N值减去x^2和2*x^2的值就是我们要的结果。

我开始时写的代码。。。。

#include <stdio.h>
#include <math.h>
#include <vector>
#include <queue>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int MAXN = 10000010;
int is_prime[MAXN];
int prime[MAXN];
int tot=0;

void find_prime()
{
    is_prime[1]=1;
    for(int i=2;i<MAXN;i++){
        if(!is_prime[i]){
            prime[tot++]=i;
            for(int j=i*2;j<MAXN;j+=i)
                is_prime[j]=1;
        }
    }
}

int power(int x,int n)
{
    int res=1;
    while(n){
        if(n&1) res=res*x;
        x=x*x;
        n>>=1;
    }
    return res;
}

int solve(int n)
{
    int num;
    while(n%2==0){
    	n/=2;
    }
    for(int i=1;i<tot&&n;i++){
        num=0;
        if(n%prime[i]==0){
            while(n%prime[i]==0){
                n/=prime[i];
                num++;
            }
        }
        int sum=(power(prime[i],num+1)-1);
        if((sum/(prime[i]-1))%2==0) return 1;
    }
    return 0;
}

int main()
{
    find_prime();
    int t;
    scanf("%d",&t);
    int xp=1;
    while(t--){
        int n;
        scanf("%d",&n);
        int ans=0;
        for(int i=3;i<=n;i++){
	        if(solve(i)) ans++;
	    }
        printf("Case %d: %d\n",xp++,ans);
    }
    return 0;
}

利用上述代码打表找到规律。

AC代码：

#include <stdio.h>
#include <math.h>
#include <vector>
#include <queue>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int main()
{
	int t;
	scanf("%d",&t);
	int xp=1;
	while(t--){
		LL n;
		scanf("%lld",&n);
		LL num1=(LL)sqrt((double)n);
		LL num2=(LL)sqrt((double)n/2.0);
		printf("Case %d: %lld\n",xp++,n-num1-num2);
	}
	return 0;
}