筛质数
线性筛模板
void init()//线性筛 { for(int i=2;i<N;i++) { if(!st[i]) prime[cnt++]=i;//假如是质数 for(int j=0;prime[j]*i<N;j++)//用这个质数把合数全筛掉 { st[prime[j]*i]=true; if(i%prime[j]==0) break; } } }
1.哥德巴赫猜想（Goldbach’s Conjecture）
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int prime[N],cnt;//存质数 bool st[N];//标记合数 int n; void init()//线性筛 { for(int i=2;i<N;i++) { if(!st[i]) prime[cnt++]=i;//假如是质数 for(int j=0;prime[j]*i<N;j++)//用这个质数把合数全筛掉 { st[prime[j]*i]=true; if(i%prime[j]==0) break; } } } int main() { init();//预处理 while(scanf("%d",&n),n) { for(int i=0;i<cnt;i++)//枚举所有质数 { int b=n-prime[i]; if(!st[b])//假如这个也是质数 { printf("%d = %d + %d\n",n,prime[i],b); break; } } } return 0; }
2.夏洛克和他的女朋友（Sherlock and His Girlfriend）
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
我们将质数染成第一种颜色，合数染成第二种颜色
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int prime[N],cnt;//存质数 bool st[N];//标记合数 int n; void init()//线性筛 { for(int i=2;i<N;i++) { if(!st[i]) prime[cnt++]=i;//假如是质数 for(int j=0;prime[j]*i<N;j++)//用这个质数把合数全筛掉 { st[prime[j]*i]=true; if(i%prime[j]==0) break; } } } int main() { init();//预处理 scanf("%d",&n); if(n<=2) puts("1");//假如只有质数，只需要一种颜色即可 else puts("2");//反之两种 for(int i=2;i<=n+1;i++)//输出质数染成1，合数染成2 if(!st[i]) cout<<1<<' '; else cout<<2<<' '; return 0; }
3.质数距离
用1~50000中的质数来筛l~r区间的合数，然后在把l~r之间的质数存下来即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int prime[N],cnt;//存质数 bool st[N*10];//标记合数 void init(int n)//线性筛 { memset(st,0,sizeof st); cnt=0; for(int i=2;i<=n;i++) { if(!st[i]) prime[cnt++]=i;//假如是质数 for(int j=0;prime[j]*i<=n;j++)//用这个质数把合数全筛掉 { st[prime[j]*i]=true; if(i%prime[j]==0) break; } } } int main() { int l,r; while(cin>>l>>r) { init(50000);//预处理 memset(st,0,sizeof st);//清空合数 for(int i=0;i<cnt;i++) { ll p=prime[i]; for(ll j=max(2*p,(l+p-1)/p*p);j<=r;j+=p) st[j-l]=true;//用质数筛这个区间的合数 } cnt=0; for(int i=0;i<=r-l;i++)//把这个区间的质数存下来 if(!st[i]&&i+l>=2) prime[cnt++]=i+l; if(cnt<=1) puts("There are no adjacent primes."); else { int mad=0,mid=0; for(int i=0;i<cnt-1;i++)//更新质数之间的最大最小 { int d=prime[i+1]-prime[i]; if(d>prime[mad+1]-prime[mad]) mad=i; if(d<prime[mid+1]-prime[mid]) mid=i; } printf("%d,%d are closest, %d,%d are most distant.\n", prime[mid],prime[mid+1],prime[mad],prime[mad+1] ); } } return 0; }
分解质因数
1.阶乘分解
简单的分解质因数
1. #in#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int prime[N],cnt;//存质数 bool st[N]; void init(int n)//筛质数 { for(int i=2;i<=n;i++) { if(!st[i]) prime[cnt++]=i;//假如是质数 for(int j=0;prime[j]*i<=n;j++)//用这个质数把合数全筛掉 { st[prime[j]*i]=true; if(i%prime[j]==0) break; } } } int main() { int n; cin>>n; init(n); for(int i=0;i<cnt;i++)//枚举所有质数 { int p=prime[i]; int res=0; for(int j=n;j;j/=p) res+=j/p;//存能整除p的幂次的所有答案 cout<<p<<' '<<res<<endl; } return 0; }
快速幂
快速幂模板
int qmi(int a,int k,int p)//快速幂模板，a^k%p { int res=1; while(k) { if(k&1) res=(ll)res*a%p; a=(ll)a*a%p; k>>=1; } return res; }
1.序列的第 k 个数
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
就简单的快速幂
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=200907; int a,b,c,k; int qmi(int a,int k,int p)//快速幂模板，a^k%p { int res=1; while(k) { if(k&1) res=(ll)res*a%p; a=(ll)a*a%p; k>>=1; } return res; } void solve() { cin>>a>>b>>c>>k; if(2*b==a+c) cout<<(a+(ll)(b-a)*(k-1))%mod<<endl;//假如是等差数列 else cout<<(a*qmi(b/a,k-1,mod))%mod<<endl;//假如是等比 } int main() { int T; cin>>T; while(T--) solve(); return 0; }
2.越狱
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
用总的信仰情况-不冲突的情况即可为总的冲突可能
总的情况：每个人都有m中信仰则：m^n
不冲突，则相邻的信仰不同：第一间m中，第二间只能在（m-1）种选了，后面的也一样
则：m*(m-1)^(n-1)
答案：m^n-m*(m-1)^(n-1)，用快速幂求即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=100003; int qmi(int a,ll k,int p)//快速幂模板 { int res=1; while(k) { if(k&1) res=(ll)a*res%p; a=(ll)a*a%p; k>>=1; } return res; } int main() { int m; ll n; cin>>m>>n; cout<<(((qmi(m,n,mod)-(ll)m*qmi(m-1,n-1,mod))%mod+mod)%mod)<<endl;//因为c++模出来的数可能是负数，所以+mod变成正数 return 0; }
