登录
← 返回首页 | 代码片段 › 7 数论与数学 › 7.1 素数筛法 › 素数筛法 / 搜索
JSON MD

7.1 素数筛法

线性筛 xianxingshai
16 行
CPP JSON
【线性筛(欧拉筛 / Euler Sieve)——质数筛选】 ▪ pre(n) — 筛出 [2,n] 所有质数存入 pri 向量: 遍历 i=2..n:若 not_prime[i]==false 则 i 为质数加入 pri; 对每个已知质数 pri_j,标记 i*pri_j 为合数,若 i%pri_j==0 则 break(关键!保证每个合数只被其最小质因子筛一次) ▪ pri[] — 存储筛出的所有质数 ▪ not_prime[] — 合数标记数组 时间复杂度严格 O(N)。与传统埃氏筛 O(N log log N) 相比,常数稍大但理论更优,N 可达 1e7+。
C++ 16 行 CPP
vector<int> pri;
bool not_prime[N];
void pre(int n) {
    for (int i = 2; i <= n; i++) {
        if (!not_prime[i]) {
            pri.push_back(i);
        }
        for (int pri_j : pri) {
            if (i * pri_j > n) break;
            not_prime[i * pri_j] = true;
            if (i % pri_j == 0) {
                break;
            }
        }
    }
}
欧拉筛.返回质数的个数。 oulashai
16 行
CPP JSON
【欧拉筛(线性筛)——返回质数个数】 ▪ euler_sieve(n) — 筛出 [2,n] 所有质数并返回质数个数 cnt: 遍历 i=2..n,若 !vis[i] 则 prime[cnt++]=i;对每个已找到的质数 prime[j],标记 vis[i*prime[j]]=1,若 i%prime[j]==0 则 break。 ▪ prime[] — 按发现顺序存储质数 ▪ vis[] — 合数标记 时间复杂度严格 O(N),比 ID=24 的 `pre()` 多返回了质数个数 cnt。
C++ 16 行 CPP
int prime[MAXN];              //保存质数
int vis[MAXN];                //记录是否被筛
int euler_sieve(int n){       //欧拉筛。返回质数的个数。
    int cnt = 0;              //记录质数个数
    memset(vis,0,sizeof(vis));
    memset(prime,0,sizeof(prime));
    for(int i=2;i<=n;i++){             //检查每个数,筛去其中的合数
        if(!vis[i]) prime[cnt++]=i;    //如果没有筛过,是质数,记录。第一个质数是2
        for(int j=0; j<cnt; j++){      //用已经得到的质数去筛后面的数
            if(i*prime[j] >n)  break;  //只筛小于等于n的数
            vis[i*prime[j]]=1;         //关键1。用x的最小质因数筛去x
            if(i%prime[j]==0)  break;  //关键2。如果不是这个数的最小质因子,结束
        }
    }
    return cnt;                        //返回小于等于n的素数的个数
}
求等比数列和 二分
28 行
CPP JSON
【求等比数列和(二分)】 质数与筛法相关模板。 核心函数: void prime_devisor(int x) — Prim最小生成树 int sakura(无参数) — 后缀数组 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 27 行 CPP
#include<cstdio>
#define R register int
int n,t,px[10005],pk[10005];
inline void prime_devisor(int x){
	if(x%2==0){
		px[++t]=2;
		while(x%2==0)pk[t]++,x/=2;
	}
	for(R i=3;i*i<=x;i+=2){
		if(x%i==0){
			px[++t]=i;
			while(x%i==0)pk[t]++,x/=i;
		}
	}
	if(x!=1)px[++t]=x,pk[t]=1;
}
inline int sakura(){
	scanf("%d",&n);
	printf("%d=",n);
	prime_devisor(n);
	for(R i=1;i<=t;i++){
		printf("%d^%d",px[i],pk[i]);
		if(i<t)printf("+");
	}
}
int QAQWQ=sakura();
int main(){}
gcd 辗转相模
8 行
CPP JSON
【gcd(辗转相模)】 质数与筛法相关模板。 核心函数: int GCD(int a,int b) — 最大公约数 int gcd(int a,int b) — 最大公约数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 8 行 CPP
#include<cstdio>
int n,a,b;
inline int GCD(int a,int b){while(b^=a^=b^=a%=b);return a;}
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int main(){
	scanf("%d",&n);
	while(n--)scanf("%d%d",&a,&b),printf("%d\n",GCD(a,b));
}
Mobius函数 埃氏筛
19 行
CPP JSON
【Mobius函数(埃氏筛)】 质数与筛法相关模板。 核心函数: void get_miu(无参数) — 获取值 关键配置: N=1e7+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 18 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
const int N=1e7+3;
int i,j,n,cnt,pan[N],miu[N];
inline void get_miu(){
	for(i=1;i<=n;++i)miu[i]=1;
	for(i=2;i<=n;++i)
		if(!pan[i]){
			miu[i]=-1;
			for(j=i<<1;j<=n;j+=i)pan[j]=1,miu[j]*=(j/i%i==0)?0:-1;
		}
}
int main(){
	n=N;
	get_miu();
	for(i=1;i<=n;++i)printf("%d: %d\n",i,miu[i]);
}
Mobius函数 线筛
22 行
CPP JSON
【Mobius函数(线筛)】 质数与筛法相关模板。 核心函数: void get_miu(无参数) — 获取值 关键配置: N=1e7+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 21 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
const int N=1e7+3;
int i,j,n,cnt,pri[N>>1],pan[N],miu[N];
inline void get_miu(){
	pan[1]=1,miu[1]=1;
	for(i=2;i<=n;++i){
		if(!pan[i])pri[++cnt]=i,miu[i]=-1;
		for(j=1;j<=cnt&&i*pri[j]<=n;++j){
            pan[i*pri[j]]=1;
            if(i%pri[j])miu[i*pri[j]]=-miu[i];
            else{miu[i*pri[j]]=0;break;}
        }
	}
}
int main(){
	n=N;
	get_miu();
	for(i=1;i<=n;++i)printf("%d: %d\n",i,miu[i]);
}
最值反演 (Card Collector) Min-Max容斥
30 行
CPP JSON
【最值反演 (Card Collector)(Min-Max容斥)】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 关键配置: N=23,M=1048576+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 29 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=23,M=1048576+3;
int n,V,cnt[M];LD ans,p[N],Min[M];
inline void in(Re &x){
    int f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=f?-x:x;
}
int main(){
//    freopen("123.txt","r",stdin);
    while(~scanf("%d",&n)){
        V=(1<<n)-1,ans=0;
        for(Re i=1;i<=n;++i)scanf("%lf",&p[i]);
        for(Re s=1;s<=V;++s){
            Min[s]=0,cnt[s]=cnt[s>>1]+(s&1);
            for(Re i=1;i<=n;++i)if(s&(1<<i-1))Min[s]+=p[i];
            Min[s]=1.0/Min[s];
        }
        for(Re t=1;t<=V;++t)ans+=(cnt[t]&1)?Min[t]:-Min[t];
        printf("%lf\n",ans);
    }
}
杜教筛 map
56 行
CPP JSON
【杜教筛(map)】 杜教筛模板,O(N^(2/3)) 求积性函数前缀和。 核心函数: void in(Re &x) — 核心算法函数 void get_(Re N) — 获取值 LL get_Sphi(Re n) — 获取值 int get_Smiu(Re n) — 获取值 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 55 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Re register int
#define LL long long
using namespace std;
const int N23=1664511+3,N=2147483647;
int x,T,cnt,pan[N23],pri[N23],phi[N23],miu[N23];
int TO,Smiu[N23];LL Sphi[N23];
map<int,int>Smiu_;map<int,LL>Sphi_;
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void get_(Re N){
	miu[1]=phi[1]=pan[1]=1;
	for(Re i=2;i<=N;++i){
		if(!pan[i])pri[++cnt]=i,miu[i]=-1,phi[i]=i-1;
		for(Re j=1;j<=cnt&&pri[j]<=N/i;++j){
			pan[i*pri[j]]=1;
			if(i%pri[j])miu[i*pri[j]]=-miu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]];
			else{miu[i*pri[j]]=0,phi[i*pri[j]]=phi[i]*pri[j];break;}
		}
	}
	for(Re i=1;i<=N;++i)Smiu[i]=Smiu[i-1]+miu[i],Sphi[i]=Sphi[i-1]+phi[i];
}
inline LL get_Sphi(Re n){
	if(n<=TO)return Sphi[n];
	if(Sphi_[n])return Sphi_[n];
	LL ans=(LL)n*(n+1)>>1;
	for(Re l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		ans-=(LL)(r-l+1)*get_Sphi(n/l);
	}
	return Sphi_[n]=ans;
}
inline int get_Smiu(Re n){
	if(n<=TO)return Smiu[n];
	if(Smiu_[n])return Smiu_[n];
	Re ans=1;
	for(Re l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		ans-=(r-l+1)*get_Smiu(n/l);
	}
	return Smiu_[n]=ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(T),get_(TO=N23-3);
	while(T--)in(x),printf("%lld %d\n",get_Sphi(x),get_Smiu(x));
}
杜教筛 数组记忆化
63 行
CPP JSON
【杜教筛(数组记忆化)】 杜教筛模板,O(N^(2/3)) 求积性函数前缀和。 核心函数: void in(Re &x) — 核心算法函数 void get_(Re N) — 获取值 LL get_Sphi(Re n) — 获取值 int get_Smiu(Re n) — 获取值 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 62 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define Re register int
#define LL long long
using namespace std;
const int N23=1664511+3,N13=1303,N=2147483647;
int x,T,cnt,pan[N23],pri[N23],phi[N23],miu[N23];
int TO,vis1[N13],vis2[N13],Smiu[N23],Smiu_[N13];
LL Sphi[N23],Sphi_[N13];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void get_(Re N){
	miu[1]=phi[1]=pan[1]=1;
	for(Re i=2;i<=N;++i){
		if(!pan[i])pri[++cnt]=i,miu[i]=-1,phi[i]=i-1;
		for(Re j=1;j<=cnt&&pri[j]<=N/i;++j){
			pan[i*pri[j]]=1;
			if(i%pri[j])miu[i*pri[j]]=-miu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]];
			else{miu[i*pri[j]]=0,phi[i*pri[j]]=phi[i]*pri[j];break;}
		}
	}
	for(Re i=1;i<=N;++i)Smiu[i]=Smiu[i-1]+miu[i],Sphi[i]=Sphi[i-1]+phi[i];
}
inline LL get_Sphi(Re n){
	if(n<=TO)return Sphi[n];
	Re nn=N/n;
	if(vis1[nn])return Sphi_[nn];
	LL ans=(LL)n*(n+1)>>1;
	for(Re l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		ans-=(LL)(r-l+1)*get_Sphi(n/l);
	}
	vis1[nn]=1;
	return Sphi_[nn]=ans;
}
inline int get_Smiu(Re n){
	if(n<=TO)return Smiu[n];
	Re nn=N/n;
	if(vis2[nn])return Smiu_[nn];
	Re ans=1;
	for(Re l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		ans-=(r-l+1)*get_Smiu(n/l);
	}
	vis2[nn]=1;
	return Smiu_[nn]=ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(T),get_(TO=N23-3);
	while(T--){
		in(x),printf("%lld %d\n",get_Sphi(x),get_Smiu(x));
		memset(vis1,0,sizeof(vis1));
		memset(vis2,0,sizeof(vis2));
	}
}
欧拉函数 暴力) sqrt(n
17 行
CPP JSON
【欧拉函数 暴力)(sqrt(n)】 线性筛(欧拉筛)模板,O(N) 筛出质数并可同时计算积性函数。 核心函数: int phi(Re x) — 核心算法函数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 16 行 CPP
#include<cstdio>
#define Re register int
int n;
inline int phi(Re x){
	Re ans=x;
	for(Re i=2;i*i<=x;i++)
		if(x%i==0){
			ans/=i,ans*=i-1;
			while(x%i==0)x/=i;
		}
	if(x>1)ans/=x,ans*=x-1;
	return ans;
}
int main(){
	scanf("%d",&n),printf("%d\n",phi(n));
}
欧拉函数 埃氏筛
17 行
CPP JSON
【欧拉函数(埃氏筛)】 线性筛(欧拉筛)模板,O(N) 筛出质数并可同时计算积性函数。 核心函数: void get_phi(无参数) — 获取值 关键配置: N=1e6 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 16 行 CPP
#include<cstdio>
const int N=1e6;
int cnt,n=N,phi[N/3],pan[N],pri[N];
inline void get_phi(){
	phi[1]=1;
    for(int i=2;i<=n;i++)if(!phi[i]){
    	for(int j=i;j<=n;j+=i){
            if(!phi[j])phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
    }
}
int main(){
	get_phi();
	for(int i=1;i<=n;++i)printf("%d: %d\n",i,phi[i]);
}
欧拉函数 线筛
21 行
CPP JSON
【欧拉函数(线筛)】 线性筛(欧拉筛)模板,O(N) 筛出质数并可同时计算积性函数。 核心函数: void get_phi(int N) — 获取值 关键配置: N=1e6 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 20 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
const int N=1e6;
int cnt,i,j,pan[N+1],pri[N/3],phi[N+1];
inline void get_phi(int N){
    pan[1]=1,phi[1]=1;
    for(int i=2;i<=N;++i){
        if(!pan[i])pri[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&pri[j]<=N/i;++j){
            pan[i*pri[j]]=1;
            if(i%pri[j])phi[i*pri[j]]=phi[i]*(pri[j]-1);
            else{phi[i*pri[j]]=phi[i]*pri[j];break;}
        }
    }
}
int main(){
	get_phi(N);
	for(i=1;i<=N;++i)printf("%d: %d\n",i,phi[i]);
}
Power Tower (欧拉定理) 炸勃龙弱化
48 行
CPP JSON
【Power Tower (欧拉定理)(炸勃龙弱化)】 线性筛(欧拉筛)模板,O(N) 筛出质数并可同时计算积性函数。 核心函数: void in(Re &x) — 核心算法函数 LL Phi(Re x) — 核心算法函数 LL mi(Re x,Re k,Re P) — 核心算法函数 LL sakura(Re l,Re r,Re P) — 后缀数组 关键配置: N=1e5+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 47 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#include<map>
#define LL long long
#define Re register LL
using namespace std;
const int N=1e5+3;
LL n,l,r,T,P,fu,a[N];char ch;map<LL,LL>phi;
inline void in(Re &x){
    x=fu=0;ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x=fu?-x:x;
}
inline LL Phi(Re x){
    Re ans=x,pos=x;
    if(phi.count(x))return phi[x];
    for(Re i=2;i<=sqrt(x);i++)
        if(!(x%i)){
            ans=ans/i*(i-1);
            while(!(x%i)) x/=i;
        }
    if(x>1)ans=ans/x*(x-1);
    return phi[pos]=ans;
}
inline LL mi(Re x,Re k,Re P){
    Re s=1,ok=0,flag=0;ok|=(x>=P);x%=P;
    while(k){
        if(k&1){s*=x;flag|=(ok||s>=P);s%=P;}
        x*=x;ok|=(x>=P);x%=P;k>>=1;
    }
    return s+(flag?P:0);
}
inline LL sakura(Re l,Re r,Re P){
    if(P==1|l>r)return 1;
    return mi(a[l],sakura(l+1,r,Phi(P)),P);
}
int main(){
    in(n),in(P);
    for(Re i=1;i<=n;++i)in(a[i]);
    in(T);
    while(T--){
        in(l),in(r);
    	printf("%lld\n",sakura(l,r,P)%P);
    }
}
BSGS拔山盖世 可爱的质数
38 行
CPP JSON
【BSGS拔山盖世(可爱的质数)】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 关键配置: N=1e5+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 37 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int x,y,m,P;map<int,int>B;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
//x^k = y (mod P)
//k = am-b (m=sqrt(P)+1, a\in[1,m], b\in[0,m-1])
//(x^m)^a = y x^b (mod P)
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(P),in(x),in(y),m=sqrt(P)+1;
	for(Re b=0,s=y;b<m;++b)B[s]=b,s=(LL)s*x%P;
	Re tmp=mi(x,m);
	for(Re a=1,s=1;a<=m;++a){
		s=(LL)s*tmp%P;
		if(B.find(s)!=B.end()){printf("%d\n",a*m-B[s]);return 0;}
	}
	puts("no solution");
}
CRT中国剩余定理 (P两两互质) 同余方程组
35 行
CPP JSON
【CRT中国剩余定理 (P两两互质)(同余方程组)】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 void exgcd(Re a,Re b,Re &x,Re &y) — 最大公约数 LL cf(Re x,Re k,Re P) — 核心算法函数 关键配置: N=13 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 34 行 CPP
#include<cstdio>
#define LL long long
#define Re register LL
const int N=13;
LL n,ans,lcm=1,a[N],m[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void exgcd(Re a,Re b,Re &x,Re &y){
	if(!b){x=1,y=0;return;}
	exgcd(b,a%b,x,y);Re x0=x,y0=y;
	x=y0,y=x0-a/b*y0;return;
}
inline LL cf(Re x,Re k,Re P){
	Re s=0;
	while(k){
		if(k&1)(s+=x)%=P;
		(x+=x)%=P,k>>=1;
	}
	return s;
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i)in(m[i]),in(a[i]),lcm*=m[i];
    for(Re i=1;i<=n;++i){
		Re x,y,M=lcm/m[i];exgcd(M,m[i],x,y);//M[i]*inv+m[i]*y=1
		x=(x%m[i]+m[i])%m[i],(ans+=cf(cf(a[i],M,lcm),x,lcm))%=lcm;
	}
	printf("%lld\n",ans);
}
EXBSGS扩展拔山盖世 mi
50 行
CPP JSON
【EXBSGS扩展拔山盖世】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k,Re P) — 核心算法函数 int gcd(Re a,Re b) — 最大公约数 void exBSGS(Re x,Re y,Re P) — SG函数计算 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 49 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#define LL long long
#define Re register int
using namespace std;
int x,y,z;map<int,int>B;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k,Re P){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int gcd(Re a,Re b){return !b?a:gcd(b,a%b);}
inline void exBSGS(Re x,Re y,Re P){
	if(y==1){puts("0");return;}
	Re d=gcd(x,P),tmp=1,t=0;
	while(d!=1){
		if(y%d){puts("No Solution");return;}
		++t,y/=d,P/=d,tmp=(LL)tmp*(x/d)%P;
		if(y==tmp){printf("%d\n",t);return;}
		d=gcd(x,P);
	}
	Re m=sqrt(P)+1;B.clear();
	for(Re b=0,s=y;b<m;++b)B[s]=b,s=(LL)s*x%P;
	Re s=tmp;tmp=mi(x,m,P);
	for(Re a=1;a<=m;++a){
		s=(LL)s*tmp%P;
		if(B.find(s)!=B.end()){printf("%d\n",a*m-B[s]+t);return;}
	}
	puts("No Solution");
}
int main(){
//	freopen("123.txt","r",stdin);
	while(1){
		in(x),in(y),in(z);
		if(!x&&!y&&!z)break;
		exBSGS(x,z,y);
	}
}
EXCRT扩展中国剩余定理 P不一定两两互质
38 行
CPP JSON
【EXCRT扩展中国剩余定理(P不一定两两互质)】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 LL exgcd(Re a,Re b,Re &x,Re &y) — 最大公约数 LL cf(Re x,Re k,Re P) — 核心算法函数 关键配置: N=1e5+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 37 行 CPP
#include<cstdio>
#define LL long long
#define Re register LL
const int N=1e5+3;
LL n,ans,lcm=1,a[N],m[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline LL exgcd(Re a,Re b,Re &x,Re &y){
	if(!b){x=1,y=0;return a;}
	Re gcd=exgcd(b,a%b,x,y);Re x0=x,y0=y;
	x=y0,y=x0-a/b*y0;return gcd;
}
inline LL cf(Re x,Re k,Re P){
	Re s=0;
	while(k){
		if(k&1)(s+=x)%=P;
		(x+=x)%=P,k>>=1;
	}
	return s;
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i)in(m[i]),in(a[i]),lcm*=m[i];
    ans=a[1]%m[1],lcm=m[1];
    for(Re i=2;i<=n;++i){//ans+lcm*k=a[i](mod m[i]) -> lcm*k=a[i]-ans(mod m[i]) -> lcm*k+m[i]*y=a[i]-ans
		Re c=((a[i]-ans)%m[i]+m[i])%m[i],x,y;
		Re gcd=exgcd(lcm,m[i],x,y);
		Re k=cf(x,c/gcd,m[i]/gcd);
		ans+=lcm*k,lcm*=m[i]/gcd,ans=(ans%lcm+lcm)%lcm;
	}
	printf("%lld\n",ans);
}
EXGCD 线性同余方程
13 行
CPP JSON
【EXGCD(线性同余方程)】 质数与筛法相关模板。 核心函数: void exgcd(Re a,Re b,Re &x,Re &y) — 最大公约数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 12 行 CPP
#include<cstdio>
#define Re register int
int a,b,x,y;
inline void exgcd(Re a,Re b,Re &x,Re &y){
	if(!b){x=1,y=0;return;}
	exgcd(b,a%b,x,y);Re x0=x,y0=y;
	x=y0,y=x0-a/b*y0;return;
}
int main(){
    scanf("%d%d",&a,&b),exgcd(a,b,x,y);
	printf("%d\n",(x%b+b)%b);
}
二次剩余 mi
56 行
CPP JSON
【二次剩余】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 CP mi_(CP x,Re k) — 核心算法函数 LL Sqrt(Re n) — 开平方 核心结构体:CP 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 55 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
int n,T,P,W,det;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
struct CP{
	int x,y;CP(Re X=0,Re Y=0){x=X,y=Y;}
	inline CP operator*(const CP &O)const{return CP(((LL)x*O.x%P+(LL)y*O.y%P*W%P)%P,((LL)x*O.y%P+(LL)y*O.x%P)%P);}
	inline CP operator*=(const CP &O){return *this=*this*O;}
};
inline CP mi_(CP x,Re k){
	CP s=CP(1,0);
	while(k){
		if(k&1)s*=x;
		x*=x,k>>=1;
	}
	return s;
}
inline LL Sqrt(Re n){
    if(!n)return 0;Re x;
    while(1){
        x=rand()%P,W=((LL)x*x%P-n+P)%P;
        if(mi(W,(P-1)/2)==P-1)break;
    }
    return mi_(CP(x,1),(P+1)/2).x;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(T);
	while(T--){
		in(n),in(P);
		if(mi(n,(P-1)/2)==P-1)puts("Hola!");//�޽�
	    else{
		    det=Sqrt(n);
		    if(det)printf("%d %d\n",min(det,P-det),max(det,P-det));
		    else printf("%d\n",det);
		}
	}
}
扩展欧拉定理 a^b%m
26 行
CPP JSON
【扩展欧拉定理(a^b%m)】 线性筛(欧拉筛)模板,O(N) 筛出质数并可同时计算积性函数。 核心函数: LL cf(Re x,Re k) — 核心算法函数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 25 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cctype>
#define LL long long
#define Re register LL
LL i,a,b,m,x,s,phi,flag;char c;
inline LL cf(Re x,Re k){
	Re s=0;
	while(k){
		if(k&1)(s+=x)%=m;
		(x<<=1)%=m,k>>=1;
	}
	return s;
}
int main(){
    scanf("%lld%lld",&a,&m);phi=x=m;
    for(i=2;i*i<=m;++i)if(!(x%i)){phi-=phi/i;while(!(x%i))x/=i;}
    if(x>1)phi-=phi/x;
    while(!isdigit(c=getchar()));
    while(isdigit(c))flag|=((b=(b<<1)+(b<<3)+(c^48))>=phi),b%=phi,c=getchar();
    b+=flag?phi:0;x=1;
    while(b){if(b&1)x=cf(x,a)%m;a=cf(a,a)%m,b>>=1;}
    printf("%lld",x);
}
有理数取模 mi
25 行
CPP JSON
【有理数取模】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 LL mi(Re x,Re k) — 核心算法函数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 25 行 CPP
#include<cstdio>
#define LL long long
#define Re register LL
using namespace std;
const LL N=1e4+3,P=19260817;
LL a,b;
inline void in(Re &x){
    Re f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),x%=P,c=getchar();
}
inline LL mi(Re x,Re k){
    Re s=1;
    while(k){
        if(k&1)(s*=x)%=P;
        (x*=x)%=P,k>>=1;
    }
    return s;
}
int main(){
    // freopen("123.txt","r",stdin);
    in(a),in(b);
    if(b)printf("%lld\n",a%P*mi(b,P-2)%P);
    else puts("Angry!");
}
逆元 快速幂
17 行
CPP JSON
【逆元(快速幂)】 质数与筛法相关模板。 核心函数: int inv(Re x,Re P) — 求模逆元 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 16 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
int n,P;
inline int inv(Re x,Re P){
    Re s=1,k=P-2;
    while(k){
    	if(k&1)s=(LL)s*x%P;
    	x=(LL)x*x%P,k>>=1;
    }
    return s%P;
}
int main(){
    scanf("%d%d",&n,&P);
    for(Re i=1;i<=n;++i)printf("%d\n",inv(i,P));
}
逆元 递推
12 行
CPP JSON
【逆元(递推)】 质数与筛法相关模板。 关键配置: N=3e6+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 11 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
const int N=3e6+3;
int n,P,inv[N];
int main(){
    scanf("%d%d",&n,&P);
    inv[1]=1;
    for(Re i=2;i<=n;++i)inv[i]=(LL)(P-P/i)*inv[P%i]%P;
    for(Re i=1;i<=n;++i)printf("%d\n",inv[i]);
}
炸勃龙 树状数组+扩展欧拉定理
47 行
CPP JSON
【炸勃龙(树状数组+扩展欧拉定理)】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re k) — 加法更新 LL ask(Re x) — 核心算法函数 LL mi(Re x,Re k,Re P) — 核心算法函数 LL sakura(Re l,Re r,Re P) — 后缀数组 关键配置: N=5e5+3,Np=2e7 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 46 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#define LL long long
#define Re register LL
#define F(a,b) for(i=a;i<=b;++i)
const int N=5e5+3,Np=2e7;
LL i,j,n,x,l,r,K,T,fu,cnt,c[N],C[N],pan[Np+1],pri[Np+1],phi[Np+1];char ch;
inline void in(Re &x){
    x=fu=0;ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x=fu?-x:x;
}
inline void add(Re x,Re k){while(x<=n)C[x]+=k,x+=x&-x;}
inline LL ask(Re x){Re tmp=0;while(x)tmp+=C[x],x-=x&-x;return tmp;}
inline LL mi(Re x,Re k,Re P){
    Re s=1,ok=0,flag=0;ok|=(x>=P);x%=P;
    while(k){
        if(k&1){s*=x;flag|=(ok||s>=P);s%=P;}
        x*=x;ok|=(x>=P);x%=P;k>>=1;
    }
    return s+(flag?P:0);
}

inline LL sakura(Re l,Re r,Re P){
    if(P==1|l>r)return 1;
    return mi(ask(l),sakura(l+1,r,phi[P]),P);
}
int main(){
    for(i=2;i<=Np;++i){
        if(!pan[i])pri[++cnt]=i,phi[i]=i-1;
        for(j=1;j<=cnt;++j){
      		if(i*pri[j]>Np)break;
      		pan[i*pri[j]]=1;
      		if(i%pri[j])phi[i*pri[j]]=phi[i]*(pri[j]-1);
      		else{phi[i*pri[j]]=phi[i]*pri[j];break;}
   		}
    }
    in(n),in(T);
    F(1,n)in(x),add(i,x-l),l=x;
    while(T--){
        in(K),in(l),in(r),in(x);
        if(K<2)add(l,x),add(r+1,-x);
        else printf("%lld\n",sakura(l,r,x)%x);
    }
}
判素数 Miller Rabin
40 行
CPP JSON
【判素数(Miller Rabin)】 质数与筛法相关模板。 核心函数: LL cf(Re x,Re k,Re P) — 核心算法函数 LL mi(Re x,Re k,Re P) — 核心算法函数 bool Miller_Rabin(Re x) — 核心算法函数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 39 行 CPP
#include<cstdio>
#define LL long long
#define Re register LL
LL n,prime[10]={2,3,5,7,11,13,17,19,23,29};
inline LL cf(Re x,Re k,Re P){
	Re s=0;
	while(k){
		if(k&1)(s+=x)%=P;
		(x<<=1)%=P,k>>=1;
	}
	return s%P;
}
inline LL mi(Re x,Re k,Re P){
	Re s=1;
    while(k){
    	if(k&1)s=cf(s,x,P)%P;
    	x=cf(x,x,P)%P,k>>=1;
    }
    return s%P;
}
inline bool Miller_Rabin(Re x){
    Re s=0,t=x-1;
    if(x==2)return 1;
    if(x<2||!(x&1))return 0;
    while(!(t&1))s++,t>>=1;
    for(Re i=0;i<10&&prime[i]<x;++i){
        Re a=prime[i],b=mi(a,t,x);
        for(Re j=1,k;j<=s;++j){
            k=cf(b,b,x);
            if(k==1&&b!=1&&b!=x-1)return 0;
            b=k;
        }
        if(b!=1)return 0;
    }
    return 1;
}
int main(){
	while(scanf("%lld",&n)!=EOF)puts(Miller_Rabin(n)?"Y":"N");
}
判素数 暴力
16 行
CPP JSON
【判素数(暴力)】 质数与筛法相关模板。 核心函数: bool judge(int n) — 判定函数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 15 行 CPP
#include<cstdio>
#include<cmath>
int x;
inline bool judge(int n){
	if(n<4)return 1;
	if(n%2==0)return 0;
	int half=sqrt(n);
	for(int i=3;i<=half;i+=2)
		if(n%i==0)return 0;
	return 1;
}
int main(){
	scanf("%d",&x);
	puts(judge(x)?"YES":"NO");
}
筛素数 埃氏筛
17 行
CPP JSON
【筛素数(埃氏筛)】 质数与筛法相关模板。 核心函数: void creat_prime(无参数) — Prim最小生成树 int sakura(无参数) — 后缀数组 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 16 行 CPP
#include<cstdio>
#define R register int
int pri[10005],pan[10005],gs;
inline void creat_prime(){
	for(R i=2;i<=10000;i++)
		if(pan[i]==0){
			pri[++gs]=i;
			for(R j=2;i*j<=10000;j++)pan[i*j]=1;
		}
}
inline int sakura(){
	creat_prime();
	for(R i=1;i<=gs;i++)printf("%d\n",pri[i]);
}
int QAQWQ=sakura();
int main(){}
筛质数 线筛
18 行
CPP JSON
【筛质数(线筛)】 质数与筛法相关模板。 核心函数: void get_pri(无参数) — 获取值 关键配置: N=1e6 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 18 行 CPP
#include<cstdio>
#include<ctime>
const int N=1e6;
int cnt,i,j,pri[N/3];bool pan[N+1];
inline void get_pri(){
	pan[0]=pan[1]=1;
	for(i=2;i<=N;++i){
		if(!pan[i])pri[++cnt]=i;
		for(j=1;j<=cnt&&i*pri[j]<=N;++j){
			pan[i*pri[j]]=1;
			if(i%pri[j]==0)break;
		}
	}
}
int main(){
	get_pri();
	for(j=0,i=1;i<=cnt;++i)printf("%d ",pri[i]);
}
已复制