首页 > 代码库 > UVa10539

UVa10539

2024-08-14 03:29:56   219人阅读

http://vjudge.net/problem/UVA-10539

 

先打出来sqrt(n)以内的素数表，然后对于每个素数x，他对答案的贡献就是最大的p使x^p<=n，即log(x,n)。注意精度误差。 
用1..r的减去1..l-1的就是答案。

 

 1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 const int mxn=1200000;10 int pri[mxn],cnt=0;11 bool vis[mxn];12 int num[mxn];13 void Pri(){14     cnt=0;int i,j;15     for(i=2;i<mxn;i++){16         if(!vis[i])pri[++cnt]=i;17         for(j=1;j<=cnt && i*pri[j]<mxn;j++){18             vis[i*pri[j]]=1;19             if(i%pri[j]==0)break;20         }21     }22     return;23 }24 LL query(LL n){25     LL ans=0;26     int i,j;27     for(i=1;i<=cnt && (LL)pri[i]*pri[i]<=n;i++){28         ans+=log(n+0.1)/log(pri[i])-1;29     }30     return ans;31 }32 int n;33 LL l,r;34 int main(){35     Pri();36     int T;37     scanf("%d",&T);38     while(T--){39         scanf("%lld%lld",&l,&r);40         printf("%lld\n",query(r)-query(l-1));41     }42     return 0;43 }

 

UVa10539


联系
我们