山东省建设发展研究院网站,c++培训班学费一般多少,网页版攻速传奇,网站做优化好还是推广好题意大概就是让你求一下[L,R]中的约数个数是素数的数的个数。 其中1LR1e12,R-L1e6. 然后我写了两种做法#xff0c;第一种是可以直接搞出来L-R的约数个数#xff0c;然后直接统计一下就好了。 这个的复杂度大致是 O((R-L) * log(R-L)) 第二种就是需要先发现满…题意大概就是让你求一下[L,R]中的约数个数是素数的数的个数。 其中1LR1e12,R-L1e6. 然后我写了两种做法第一种是可以直接搞出来L-R的约数个数然后直接统计一下就好了。 这个的复杂度大致是 O((R-L) * log(R-L)) 第二种就是需要先发现满足条件的数必须只能是一个质数的一个质数-1次方所以直接筛。 这个的复杂度大致是 O((R-L) * 一个小于log的可以看成常数的东西) 最后需要注意一下1是不合法的我这两种做法一开始都把1算进来了2333 code1: #includebits/stdc.h
#define ll long long
using namespace std;
const int maxn1000000;
int zs[maxn/2],t0,T,ans;
bool v[maxn5];
int d[maxn5],derta;
ll l,r,lef[maxn5];inline void init(){for(int i2;imaxn;i){if(!v[i]) zs[t]i;for(int j1,u;jt(uzs[j]*i)maxn;j){v[u]1;if(!(i%zs[j])) break;}}
}inline void solve(){scanf(%lld%lld,l,r),dertar-l;fill(d,dderta1,1),ans0;for(int i0;iderta;i) lef[i]i(ll)l;for(int i1;itzs[i]*(ll)zs[i]r;i)for(int j(l-1)/zs[i]*(ll)zs[i](ll)zs[i]-l,now;jderta;jzs[i]){now1;while(!(lef[j]%zs[i])) lef[j]/zs[i],now;d[j]*now;}for(int i0;iderta;i){if(lef[i]!1) d[i]*2;if(!v[d[i]]) ans;}if(l1) ans--;printf(%d\n,ans);
}int main(){init();scanf(%d,T);while(T--) solve();return 0;
}code2: #includebits/stdc.h
#define ll long long
using namespace std;
const int maxn1000000;
int zs[maxn/2],t0,T,ans,derta;
bool v[maxn5],vis[maxn5];
ll l,r;inline void init(){for(int i2;imaxn;i){if(!v[i]) zs[t]i;for(int j1,u;jt(uzs[j]*i)maxn;j){v[u]1;if(!(i%zs[j])) break;}}
}inline void solve(){scanf(%lld%lld,l,r),dertar-l;memset(vis,0,sizeof(vis)),ans0; for(int i1;itzs[i]*(ll)zs[i]r;i){for(ll jzs[i],u2;jr;j*(ll)zs[i],u) if(!v[u]jl) ans;for(int jr/zs[i]*zs[i]-l;j0;j-zs[i]) vis[j]1;}for(int i0;iderta;i) if(!vis[i]) ans;if(l1) ans--;printf(%d\n,ans);
}int main(){init();scanf(%d,T);while(T--) solve();return 0;
}转载于:https://www.cnblogs.com/JYYHH/p/8612365.html
