admin管理员组文章数量:1593971
H - Interesting Numbers
URAL - 2070input | output |
---|---|
3 7 | 4 |
2 2 | 1 |
77 1010 | 924 |
题目链接:https://cn.vjudge/contest/160744#problem/H
不难的一个数论题,题目的意思是说让你求在L,R区间里,同时满足或者同事不满足素数和这个数的约数个数是素数的要求的数的个数。。有点绕。
我们先用素数筛求出1e6以内的素数,然后我们用唯一分解定理来求约数个数
代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#define LL long long
using namespace std;
const int maxn=1000010;
LL vis[maxn];
LL p[maxn];
int sum;
void getprime(){
sum=1;
for(LL i=2;i<=maxn;i++){
if(vis[i]==0){
p[sum++]=i;
for(LL j=i*2;j<=maxn;j+=i){
vis[j]=1;
}
}
}
}
LL solve(LL x){
LL ret=x;
for(int i=1;i<sum;i++){
LL t=(LL)p[i]*p[i];
int k=2;
for(;t<=x;k++,t=t*p[i]){
if(!vis[k+1]){//判断2条件是不是满足
ret--;//只满足一个条件
}
}
}
return ret;
}
int main(){
getprime();
LL L,R;
while(~scanf("%lld%lld",&L,&R)){
LL ans=solve(R)-solve(L-1);
cout<<ans<<endl;
}
return 0;
}
本文标签: 素数定理分解NUMBERSInteresting
版权声明:本文标题:H - Interesting Numbers URAL - 2070 ----素数筛+唯一分解定理 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1728179885a1148290.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论