題意大概就是讓你求一下[L,R]中的約數(shù)個數(shù)是素?cái)?shù)的數(shù)的個數(shù)。

其中1<=L<=R<=1e12,R-L<=1e6.

?

然后我寫了兩種做法，第一種是可以直接搞出來L-R的約數(shù)個數(shù)，然后直接統(tǒng)計(jì)一下就好了。

這個的復(fù)雜度大致是 O((R-L) * log(R-L))

第二種就是需要先發(fā)現(xiàn)滿足條件的數(shù)必須只能是一個質(zhì)數(shù)的一個質(zhì)數(shù)-1次方，所以直接篩。

這個的復(fù)雜度大致是 O((R-L) * 一個小于log的可以看成常數(shù)的東西)

?

最后需要注意一下1是不合法的，我這兩種做法一開始都把1算進(jìn)來了2333

?

code1:

#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=1000000; int zs[maxn/2],t=0,T,ans; bool v[maxn+5]; int d[maxn+5],derta; ll l,r,lef[maxn+5];inline void init(){for(int i=2;i<=maxn;i++){if(!v[i]) zs[++t]=i;for(int j=1,u;j<=t&&(u=zs[j]*i)<=maxn;j++){v[u]=1;if(!(i%zs[j])) break;}} }inline void solve(){scanf("%lld%lld",&l,&r),derta=r-l;fill(d,d+derta+1,1),ans=0;for(int i=0;i<=derta;i++) lef[i]=i+(ll)l;for(int i=1;i<=t&&zs[i]*(ll)zs[i]<=r;i++)for(int j=(l-1)/zs[i]*(ll)zs[i]+(ll)zs[i]-l,now;j<=derta;j+=zs[i]){now=1;while(!(lef[j]%zs[i])) lef[j]/=zs[i],now++;d[j]*=now;}for(int i=0;i<=derta;i++){if(lef[i]!=1) d[i]*=2;if(!v[d[i]]) ans++;}if(l==1) ans--;printf("%d\n",ans); }int main(){init();scanf("%d",&T);while(T--) solve();return 0; }

?code2:

#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=1000000; int zs[maxn/2],t=0,T,ans,derta; bool v[maxn+5],vis[maxn+5]; ll l,r;inline void init(){for(int i=2;i<=maxn;i++){if(!v[i]) zs[++t]=i;for(int j=1,u;j<=t&&(u=zs[j]*i)<=maxn;j++){v[u]=1;if(!(i%zs[j])) break;}} }inline void solve(){scanf("%lld%lld",&l,&r),derta=r-l;memset(vis,0,sizeof(vis)),ans=0; for(int i=1;i<=t&&zs[i]*(ll)zs[i]<=r;i++){for(ll j=zs[i],u=2;j<=r;j*=(ll)zs[i],u++) if(!v[u]&&j>=l) ans++;for(int j=r/zs[i]*zs[i]-l;j>=0;j-=zs[i]) vis[j]=1;}for(int i=0;i<=derta;i++) if(!vis[i]) ans++;if(l==1) ans--;printf("%d\n",ans); }int main(){init();scanf("%d",&T);while(T--) solve();return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/JYYHH/p/8612365.html

總結(jié)

以上是生活随笔為你收集整理的Codechef Yet another cute girl的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。