| 等 级 | |
| 排 名 | 924 |
| 经 验 | 3471 |
| 参赛次数 | 0 |
| 文章发表 | 31 |
| 年 龄 | 0 |
| 在职情况 | 学生 |
| 学 校 | |
| 专 业 |
自我简介：
TA的其他文章
| 发工资咯 （贪心法） 浏览：1080 |
| 公交汽车 （可同等于完全背包问题） 浏览：408 |
| 蓝桥杯算法训练VIP-拦截导弹 （O(n*log n)量级） 浏览：608 |
你可能喜欢
评论区
```
#include<iostream>
using namespace std;
typedef long long LL;
const int N=1500000,M=100010;
int vis[N],prime[M];
LL f[M];
int main(){
ios::sync_with_stdio(false);
int n,tot=0;
cin>>n;
if(n==0){
cout<<'0';
return 0;
}
for(int i=2;i*i<=N;i++){
if(!vis[i]){
for(int j=i*i;j<=N;j+=i){
vis[j]=1;
}
}
}
for(int i=2;i<N;i++){
if(!vis[i]){
prime[tot++]=i;
}
}
f[0]=2;
for(int i=1;i<n;i++){
//a*b mod n = (a mod n)(b mod n)mod n-
f[i]=((f[i-1]%50000)*(prime[i]%50000))%50000;
}
cout<<f[n-1]<<'\n';
return 0;
}
```
如果输入的测试数据是0的话,数组会出现下溢出.
coder 2022-02-10 13:25:47 |
特判可解
coder 2022-02-10 14:28:14 |
#include<iostream> using namespace std; typedef long long LL; const int N=1500000,M=100010; int vis[N],prime[M]; LL f[M]; int main(){ ios::sync_with_stdio(false); int n,tot=0; cin>>n; if(n==0){ cout<<'0'; return 0; } for(int i=2;i*i<=N;i++){ if(!vis[i]){ for(int j=i*i;j<=N;j+=i){ vis[j]=1; } } } for(int i=2;i<N;i++){ if(!vis[i]){ prime[tot++]=i; } } f[0]=2; for(int i=1;i<n;i++){ //a*b mod n = (a mod n)(b mod n)mod n- f[i]=((f[i-1]%50000)*(prime[i]%50000))%50000; } cout<<f[n-1]<<' '; return 0; }
- «
- 1
- »