nefu 825 函数版素数判定
先预处理，素数筛打表的复杂度为$O(n)$，然后可以 $O(1)$ 的时间复杂度回答每次询问(总共 $T$ 次询问)，总时间复杂度 $O(n+T)$。
#include <bits/stdc++.h>
using namespace std;
const int N=1e7;
int n,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
memset(vis,1,sizeof(vis));//标记素数为1，先假设1~N全是素数，全部初始化为1，再筛去合数。
vis[1]=0;//1不是素数
for(int i=2;i<=N;i++)
{
if(vis[i])prime[++cnt]=i;//将i加入到prime数组
for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
{
vis[i*prime[j]]=0;//将i*pirme[j]标记为合数
if(i%prime[j]==0)break;//i是prime[j]倍数，退出循环
}
}
}
int main()
{
ios::sync_with_stdio(false);
get_prime();
while(cin>>n)
{
if(vis[n])printf("YES\n");
else printf("NO\n");
}
return 0;
}
洛谷 P3383 【模板】线性筛素数
#include <bits/stdc++.h>
using namespace std;
const int N=1e8;
int n,k,t,q,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
memset(vis,1,sizeof(vis));
vis[1]=0;
for(int i=2;i<=n;i++)
{
if(vis[i])prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
{
vis[i*prime[j]]=0;
if(i%prime[j]==0)break;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>q;
get_prime();
while(q--)
{
cin>>k;
printf("%d\n",prime[k]);
}
return 0;
}
nefu 1704 知否知否，应是绿肥红瘦
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7;
ll x,y,z,t,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
memset(vis,1,sizeof(vis));
vis[1]=0;
for(int i=2;i<=N;i++)
{
if(vis[i])prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
{
vis[i*prime[j]]=0;
if(i%prime[j]==0)break;
}
}
}
bool judge(ll x)
{
if(x<=1)return 0;
for(ll i=1;prime[i]*prime[i]<=x;i++)
if(x%prime[i]==0)return 0;
return 1;
}
int main()
{
ios::sync_with_stdio(false);
get_prime();
cin>>t;
while(t--)
{
cin>>x>>y>>z;
if(judge(x+y-z))printf("yes\n");
else printf("no\n");
}
return 0;
}
nefu 587 半素数
#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
memset(vis,1,sizeof(vis));
vis[1]=0;
for(int i=2;i<=N;i++)
{
if(vis[i])prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
{
vis[i*prime[j]]=0;
if(i%prime[j]==0)break;
}
}
}
bool judge()
{
for(int i=1;prime[i]*prime[i]<=n;i++)
if(n%prime[i]==0&&vis[n/prime[i]])return 1;
return 0;
}
int main()
{
ios::sync_with_stdio(false);
get_prime();
while(cin>>n)
{
if(judge())printf("YES\n");
else printf("NO\n");
}
return 0;
}
nefu 586 纯素数
#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
memset(vis,1,sizeof(vis));
vis[1]=0;
for(int i=2;i<=N;i++)
{
if(vis[i])prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
{
vis[i*prime[j]]=0;
if(i%prime[j]==0)break;
}
}
}
bool judge(int x)
{
int a[8],len=0;
memset(a,0,sizeof(a));
while(x)
{
a[++len]=x%10;
x=x/10;
}
for(int i=1;i<=len;i++)
{
int s=0;
for(int j=i;j>=1;j--)
s=s*10+a[j];
if(!vis[s])return 0;
}
return 1;
}
int main()
{
ios::sync_with_stdio(false);
get_prime();
while(cin>>n)
{
if(judge(n))printf("YES\n");
else printf("NO\n");
}
return 0;
}
nefu 781 素数与数论
#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int a,b,cnt,prime[N+10],pre[N+10];//pre表示1~i(包括i)有多少个素数，也就是前缀和
bool vis[N+10];
void get_prime()
{
memset(vis,1,sizeof(vis));
pre[1]=0;vis[1]=0;
for(int i=2;i<=N;i++)
{
if(vis[i])prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
{
vis[i*prime[j]]=0;
if(i%prime[j]==0)break;
}
pre[i]=cnt;
}
}
int main()
{
ios::sync_with_stdio(false);
get_prime();
while(cin>>a>>b)
printf("%d\n",pre[b]-pre[a-1]);
return 0;
}
nefu 585 最大素因子
#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,cnt,prime[N+10],pre[N+10];
bool vis[N+10];
void get_prime()
{
memset(vis,1,sizeof(vis));
pre[1]=0;vis[1]=0;
for(int i=2;i<=N;i++)
{
if(vis[i])prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
{
vis[i*prime[j]]=0;
if(i%prime[j]==0)break;
}
pre[i]=cnt;//pre[i]记录i是第几个素数
}
}
int main()
{
ios::sync_with_stdio(false);
get_prime();
while(cin>>n)
{
if(n==1){printf("0\n");continue;}
for(int i=n;i>=2;i--)
if(n%i==0&&vis[i]){printf("%d\n",pre[i]);break;}
}
return 0;
}
nefu 1321 差点是素数
这题算综合大题了，素数筛打表+二分+区间合并，具体思路详见代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6;
bool vis[N+10];
ll t,l1,r1,l2,r2,l,r,tot,cnt,sum,prime[N+10],ans[N+10];
void get_prime()//素数筛打表
{
vis[1]=1;//vis为1表示为合数
for(ll i=2;i<=N;i++)
{
if(!vis[i])prime[++cnt]=i;//0表示是素数
for(ll j=1;j<=cnt&&i*prime[j]<=N;j++)
{
vis[i*prime[j]]=1;//标记j*prime[i]为合数
if(i%prime[j]==0)break;
}
}
}
void get_ans()//打表满足条件的数，存入ans数组，并排序
{
for(ll i=1;i<=cnt;i++)
for(ll j=prime[i]*prime[i];j<=1e12;j*=prime[i])
ans[++tot]=j;
sort(ans+1,ans+tot+1);//tot=80070 ans[tot]=999966000289
}
ll get_num(ll l,ll r)//求在[l,r]区间内满足条件的个数
{
ll a=lower_bound(ans+1,ans+tot+1,l)-ans;
ll b=upper_bound(ans+1,ans+tot+1,r)-ans;
//注意下限a是lower_bound，上限b是upper_bound，可以画区间的图看一下
return b-a;
}
int main()
{
ios::sync_with_stdio(false);
get_prime();get_ans();
cin>>t;
while(t--)
{
cin>>l1>>r1>>l2>>r2;
if(l2>r1||l1>r2)sum=get_num(l1,r1)+get_num(l2,r2);//区间不重叠
else//区间重叠
{
l=min(l1,l2);
r=max(r1,r2);
sum=get_num(l,r);
}
printf("%lld\n",sum);
}
return 0;
}
nefu 1262 五十弦翻塞外声
快速求一个数的因子和：唯一分解定理。
化简因子和的公式，可用等比数列求和公式：
$$1+p^1+p^2+...+p^n=\frac {p^{n+1}-1}{p-1}$$
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+3;
//小于1e12的最大素数 999999999989
//大于1e6的最小素数 1e6+3 注意打表素数筛的N>=1e6+3 否则会被999999999989这个数据卡掉
ll T,n,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
memset(vis,1,sizeof(vis));
vis[1]=0;
for(int i=2;i<=N;i++)
{
if(vis[i])prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
{
vis[i*prime[j]]=0;
if(i%prime[j]==0)break;
}
}
}
ll f(ll x)//求x的因子和
{
ll s=1;
for(ll i=1;prime[i]*prime[i]<=x;i++)//找x的素因子
{
if(x%prime[i]==0)
{
ll t=1;
while(x%prime[i]==0)
t=t*prime[i],x=x/prime[i];
s*=(t*prime[i]-1)/(prime[i]-1);
}
}
if(x>1)s*=(1+x);//若x未被除尽到1，说明最后的x还剩下一个素数没有乘到答案里面，把它乘进去
return s;
}
int main()
{
ios::sync_with_stdio(false);
get_prime();
cin>>T;
while(T--)
{
cin>>n;
printf("%lld\n",f(n));
}
return 0;
}
Comments | NOTHING