题目链接:http://acm.uestc.edu.cn/problem.php?pid=1720
题意解释:给一个数n,求[1,n]之内没有平方因子的数的个数。
题意分析:求无平方因子的个数,感觉直接求的话可能会无从下手,是吧?思维转一下,发现可以先求n之内平方因子的个数sum,然后n-sum就是所求的解。这个相对来说比较容易。接着分析:发现可以利用容斥原理,很简单,n之内有平方因子的数的个数sum =
n/(2^2) + n/(3^2)+……+n/(k^2) – n/(2^2 * 3^2)-……+……。

代码如下:

#include <stdio.h>
#include<string.h>

#define MAX 1000010

int prime[ MAX/2 ];
int a[MAX];
int cnt;
long long n;

void InitPrime(){
    int i,j;
    cnt = 0;
    memset( a,0,sizeof(a) );
    for( i=2; i<MAX; i++ ){
        if( !a[i] )
            prime[cnt++] = i;
        for( j=0; j<cnt && i*prime[j]<MAX; j++ ){
            a[ i*prime[j] ] = 1;
            if( i%prime[j] == 0 )
                break;
        }
    }
}

long long SquareRoot( int s,long long d ){
    long long sum = 0;
    while( s<cnt && (long long)prime[s]*prime[s]<=n/d ){
        sum += n/(d*prime[s]*prime[s])-SquareRoot(s+1,d*prime[s]*prime[s]);
        s++;
    }
    return sum;
}

int main(){
    int T;
    long long sum;
    scanf("%d", &T);
    InitPrime();
    while(  T — ){
        scanf("%lld", &n);
        sum = SquareRoot(0,1);
        printf( "%lld\n",n-sum );
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation