• 个人简介

    image

    一只蒟蒻。比赛偶尔发挥好,偶尔发挥差。请多指教。

    头图:

    $$\Huge{\color{blue}TYOI += \sum_{i=2022}^{\infty}me_i} $$AC绿CSPrp++\color{25ad40}\bold{\text{AC绿}}\Huge{CSP_{rp}++}

    图论编辑器

    文本比对

    代码模板

    普及 & 普及+/提高- & 提高 部分模板

    dij

    #pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
    #pragma GCC target("avx,sse2,sse3,sse4,mmx")
    #include <bits/stdc++.h>
    //万能头加火车头
    using namespace std;
    
    
    
    
    struct edge{
    	int v,w;
    	bool operator<(edge a)const{
    		return w>a.w;
    	}
    };
    const int MAXN=10001;
    int n,m,a,b,w,dis[MAXN],vis[MAXN];
    priority_queue <edge> q;
    vector<edge> v[MAXN];//存边vector
    void dij(int st){//dij yyds!!
    	memset(dis,127,sizeof dis);
    	dis[st]=0;
    	q.push((edge){st,0});
    	while(!q.empty()){
    		int f=(q.top()).v;
    		q.pop();
    		if(vis[f]) continue;
    		for(int i=0;i<v[f].size();i++){
    			edge g=v[f][i];
    			if(dis[f]+g.w<dis[g.v]){
    				dis[g.v]=dis[f]+g.w;
    				q.push((edge){g.v,dis[g.v]});
    			}
    		}
    		vis[f]=true;
    	}
    }
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){
    		cin>>a>>b>>w;
    		v[a].push_back((edge){b,w});
    	}
    	dij(1);
    	cout<<dis[n];
    	return 0;
    }
    dij`
    

    SPFA

    #pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3)
    #pragma GCC target("avx,sse2,sse3,sse4,mmx")
    #include <iostream>
    #include <queue>
    #include <cstdio>
    #include <vector>
    #include <cstring>
    using namespace std;
    struct edge{int to,num;};
    vector<edge> v[101];
    queue<int> q;
    const int inf=99999999;
    int n,m,st,en,a,b,k,dis[101],ans;
    bool book[101];
    void SPFA(int st){//关于SPFA,他已经死了
    	memset(dis,inf,sizeof dis);
    	dis[st]=0,book[st]=true;
    	q.push(st);
    	while(!q.empty()){
    		int f=q.front();
    		q.pop();
    		book[f]=false;
    		for(int i=0;i<v[f].size();i++){
    			if(dis[f]+v[f][i].num<dis[v[f][i].to]){
    				dis[v[f][i].to]=dis[f]+v[f][i].num;
    				if(!book[v[f][i].to]){
    					q.push(v[f][i].to);
    					book[v[f][i].to]=true;
    				}
    			}
    		}
    	}
    }
    void add(int a,int b,int k){
    	v[a].push_back((edge){b,k});
    }
    int main(){
    	cin>>n>>m>>st;
    	for(int i=1;i<=m;i++){
    		cin>>a>>b>>k;
    		add(a,b,k);
    	}
    	SPFA(st);
    	for(int i=1;i<=n;i++){
    		cout<<dis[i]<<" ";
    	}
    	return 0;
    }
    

    CRT&EXCRT

    #pragma GCC optimize(2)
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #define int long long
    using namespace std;
    
    int a[10007],m[10007],n,ans=0x3f3f3f3f3f3f3f3f;
    int str[30007][128];
    char cstr[128];
    int exgcd(int a,int b,int &x,int &y){
    	if(b==0){
    		x=1,y=0;
    		return a;
    	}
    	int g=exgcd(b,a%b,x,y);
    	int t=x;
    	x=y;
    	y=t-a/b*y;
    	return g;
    }
    int exCRT(){
    	int spe=a[1],lcm=m[1],e,f;
    	for(int i=2;i<=n;i++){
    		int ri=((a[i]-spe)%m[i]+m[i])%m[i];
    		int g=exgcd(lcm,m[i],e,f);
    		if(ri%g!=0) return 0x3f3f3f3f3f3f3f3f;
    		int z=(e*ri/g%(m[i])+(m[i]))%(m[i]);
    		spe=spe+z*lcm;
    		lcm=lcm/g*m[i];
    		spe=(spe%lcm+lcm)%lcm;
    	}
    	return spe;
    }
    char ch;
    int ptr;
    signed main(){
    	memset(str,-1,sizeof str);
    	scanf("%lld",&n);
    	getchar();
    	for(int i=1;i<=n;i++){
    		scanf("%s",cstr);
    		int le=strlen(cstr);
    		for(ptr=0;ptr<le;ptr++){
    			str[i][cstr[ptr]]=ptr;
    		}
    		m[i]=le;
    	}
    	//for(int i=1;i<=n;i++){
    		//for(char c=1;c<=126;c++){
    			//printf("%lld ",str[i][c]);
    		//}
    		//printf("\n");
    	//}
    	for(char c=1;c<=126;c++){
    		for(int i=1;i<=n;i++){
    			if(str[i][c]==-1) goto br;
    			a[i]=str[i][c];
    		}
    		//printf("I see U!\n");
    		//for(int i=1;i<=n;i++){
    			//printf("%lld+%lld ",a[i],m[i]);
    		//}
    		//printf("\n");
    		ans=min(ans,exCRT());
    		br:;
    	}
    	if(ans<0x3f3f3f3f3f3f) printf("%lld\n",ans+1);
    	else printf("-1\n");
    	return 0;
    }
    
    #pragma GCC optimize(2)
    #include <iostream>
    #include <queue>
    #include <cstdio>
    #define int long long
    using namespace std;
    
    int n,a[10007],m[10007],M=1,ans;
    int exgcd(int a,int b,int &x,int &y){
    	if(b==0){
    		x=1,y=0;
    		return a;
    	}
    	int d=exgcd(b,a%b,x,y);
    	int t=x;
    	x=y;
    	y=t-a/b*y;
    	return d;
    }
    signed main(){
    	scanf("%lld",&n);
    	for(int i=1;i<=n;i++){
    		scanf("%lld%lld",&m[i],&a[i]);
    		M=M*m[i];
    	}
    	for(int i=1;i<=n;i++){
    		int Mi=M/m[i];
    		int e,f;
    		int g=exgcd(Mi,m[i],e,f);
    		int Ti=((e/g)%(m[i]/g)+m[i]/g)%(m[i]/g);
    		ans=(ans+a[i]%M*Mi%M*Ti%M)%M;
    	}
    	printf("%lld",ans);
    	return 0;
    }
    

    Lucas(m less&p less)&exLucas

    #pragma GCC optimize(2)
    #include <iostream>
    #include <queue>
    #include <cstdio>
    #define int long long
    using namespace std;
    
    int t,fac[10009],inv[10009],ifac[10009];
    void init(int p){
    	fac[0]=fac[1]=inv[0]=inv[1]=ifac[0]=1;
    	for(int i=2;i<=p;i++){
    		fac[i]=fac[i-1]*i%p;
    		inv[i]=(p-p/i)*inv[p%i]%p;
    	}
    	for(int i=1;i<=p;i++){
    		ifac[i]=ifac[i-1]*inv[i]%p;
    	}
    	for(int i=0;i<=10;i++){
    		//printf("%lld,%lld,%lld\n",fac[i],ifac[i],inv[i]);
    	}
    	return;
    }
    int C(int n,int m,int p){
    	if(m>n) return 0;
    	return fac[n]*ifac[n-m]%p*ifac[m]%p;
    }
    int Lu_C(int n,int m,int p){
    	if(m==0) return 1;
    	return C(n%p,m%p,p)*Lu_C(n/p,m/p,p)%p;
    }
    int n,m,p;
    signed main(){
    	scanf("%lld",&t);
    	for(int i=1;i<=t;i++){
    		scanf("%lld%lld%lld",&n,&m,&p);
    		init(p);
    		printf("%lld\n",Lu_C(n+m,m,p));
    	}
    	return 0;
    }
    
    #pragma GCC optimize(2)
    #include <iostream>
    #include <queue>
    #include <cstdio>
    using namespace std;
    
    int qpow(int a,int b,int p){
    	int ans=1;
    	while(b){
    		if(b&1) ans=ans%p*a%p;
    		a=a%p*a%p;
    		b=b>>1;
    	}
    	return ans;
    }
    int C(int n,int m,int p){
    	if(m>n) return 0;
    	int u=1,d=1;
    	for(int i=1;i<=m;i++){
    		u=u*(n-i+1)%p;
    		d=d*i%p;
    	}
    	return u*qpow(d,p-2,p)%p;
    }
    int Lu_C(int n,int m,int p){
    	if(m==0) return 1;
    	return C(n%p,m%p,p)*Lu_C(n/p,m/p,p)%p;
    }
    int t,n,m,p;
    int main(){
    	scanf("%lld",&t);
    	for(int i=1;i<=t;i++){
    		scanf("%lld%lld%lld",&n,&m,&p);
    		printf("%lld\n",Lu_C(n,m,p));
    	}
    	return 0;
    }
    
    #pragma GCC optimize(2)
    #include <iostream>
    #include <queue>
    #include <cstdio>
    #define int long long
    using namespace std;
    int qpow(int a,int b,int p){
    	int ans=1;
    	while(b){
    		if(b&1) ans=ans%p*a%p;
    		a=a%p*a%p;
    		b=b>>1;
    	}
    	return ans;
    }
    int exgcd(int a,int b,int &x,int &y){
    	if(b==0){
    		x=1,y=0;
    		return a;
    	}
    	int d=exgcd(b,a%b,x,y);
    	int tmp=x;
    	x=y;
    	y=tmp-a/b*y;
    	return d;
    }
    int inv(int a,int p){//a^{-1}%p
    	int x,y;
    	exgcd(a,p,x,y);
    	return (x%p+p)%p;
    }
    int fac(int n,int und,int p){
    	if(n==0) return 1;
    	int pro=1,els=1;
    	for(int i=2;i<=p;i++) if(i%und) pro=pro*i%p;
    	for(int i=2;i<=n%p;i++) if(i%und) els=els*i%p;
    	return qpow(pro,n/p,p)%p*els%p*fac(n/und,und,p)%p;
    }
    int C(int n,int m,int und,int p){
    	if(m>n) return 0;
    	int a=fac(n,und,p),b=fac(m,und,p),c=fac(n-m,und,p),cnt=0;
    	for(int i=und;i<=n;i*=und) cnt+=n/i;
    	for(int i=und;i<=m;i*=und) cnt-=m/i;
    	for(int i=und;i<=n-m;i*=und) cnt-=(n-m)/i;
    	return a%p*inv(b,p)%p*inv(c,p)%p*qpow(und,cnt,p)%p;
    }
    int exLu_C(int n,int m,int p){
    	int tmp=p,sum=0;
    	for(int i=2;i*i<=tmp;i++){
    		if(tmp%i>0) continue;
    		int cnt=0,prod=1;
    		while(tmp%i==0){
    			tmp=tmp/i;
    			cnt++;
    			prod=prod*i;
    		}
    		int c=C(n,m,i,prod)%p;
    		//printf("%lld ",c);
    		sum=(sum%p+c*(p/prod)%p*inv(p/prod,prod)%p)%p;
    	}
    	if(tmp>1){
    		int c=C(n,m,tmp,tmp)%p;
    		///printf("%lld ",c);
    		sum=(sum%p+c*(p/tmp)%p*inv(p/tmp,tmp)%p)%p;
    	}
    	//printf("\n");
    	return sum;
    }
    int n,m,p;
    signed main(){
    	scanf("%lld%lld%lld",&n,&m,&p);
    	printf("%lld",exLu_C(n,m,p));
    	return 0;
    }
    

    并查集

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cstdlib>
    
    using namespace std;
    const int maxn = 500521;
    int n,m,p;
    int mi;
    int mj;
    int pi;
    int pj;
    int f[maxn];
    inline int read(){
        int x=0;int f=1;char c=getchar();
        while(c<'0'||c>'9'){
            if(c=='-')f=-f;
            c=getchar();
        }
        while(c<='9'&&c>='0'){
            x=x*10+c-'0';
            c=getchar();
        }
        return x*f;
    } 
    int query(int x){
        if(x == f[x])return x;
        else return f[x] = query(f[x]);
    }
    void merge(int x,int y){
        int f1 = query(x);
        int f2 = query(y);
        if(f1 != f2){
            if(rand()%2)f[f1] = f2;
            else f[f2] = f1;
        }
        return;
    }
    int main(){
        n = read();
        m = read();
        p = read();
        for(int i=1;i<=n;i++)f[i] = i;
        for(int i=1;i<=m;i++){
            mi = read();
            mj = read();
            merge(mi,mj);
        }
        for(int i=1;i<=p;i++){
            pi = read();
            pj = read();
            if(query(pi) == query(pj)){
                printf("Yes\n");
            }
            else printf("No\n");
        }
        
        return 0;
    }
    

    tarjan强联通

    #pragma GCC optimize(2)
    #include <bits/stdc++.h>
    using namespace std;
    
    vector<int> g[10007];
    int low[10007],dfn[10007],vis[10007],cnt,csum,numc[10007],bnc[10007];
    stack<int> stk;
    int n,m,a,b,ans;
    
    void tarjan(int u){
    	int v;
    	dfn[u]=low[u]=++cnt;
    	stk.push(u);
    	vis[u]=true;
    	for(int i=0;i<(g[u].size());i++){
    		v=g[u][i];
    		if(dfn[v]==0){
    			tarjan(v);
    			low[u]=min(low[u],low[v]);
    		}else{
    			if(vis[v])
    				low[u]=min(low[u],dfn[v]);
    		}
    	}
    	if(dfn[u]==low[u]){//源点 
    		csum++;
    		do{//出栈 
    			numc[csum]++;
    			v=stk.top();
    			stk.pop();
    			bnc[v]=cnt;
    			vis[v]=false;
    		}while(u!=v);
    	}
    }
    
    void add(int a,int b){
    	g[a].push_back(b);
    }
    
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){
    		cin>>a>>b;
    		add(a,b);
    	}
    	for(int i=1;i<=n;i++){
    		if(dfn[i]==0){
    			tarjan(i);
    		}
    	}
    	for(int i=1;i<=csum;i++){
    		if(numc[i]>1) ans++; 
    	}
    	cout<<ans;
    	return 0;
    }
    

    tarjan-割点,割边(桥)

    #include <iostream>
    #include <vector>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    vector<int> g[107];
    int dfn[107],low[107],root=1;
    bool vis[107];
    int n,m,a,b,cnt=0,f,x,ans;
    
    void tarjan(int u,int fa){
    	dfn[u]=low[u]=++cnt;
    	int child=0;
    	for(int i=0;i<g[u].size();i++){
    		int v=g[u][i];
    		if(dfn[v]==0){
    			child++;
    			tarjan(v,u);
    			low[u]=min(low[u],low[v]);
    			if(low[v]>=dfn[u]){
    				if(child>1||u!=1) vis[u]=true;
    			}
    		}else{
    			if(v!=fa){
    				low[u]=min(low[u],dfn[v]);
    			}
    	
    		}
    	}
    }
    
    int main(){
    	while(true){
    		memset(vis,false,sizeof vis);
    		memset(dfn,0,sizeof dfn);
    		memset(low,0,sizeof low);
    		cin>>n;
    		if(n==0) break;
    		for(int i=1;i<=n;i++){
    			g[i].clear();
    		}
    		while(true){
    			cin>>f;
    			if(f==0) break;
    			for(int i=1;i<n;i++){
    				cin>>x;
    				g[f].push_back(x);
    				g[x].push_back(f);
    				if(cin.get()=='\n') break;
    			}
    		}
    		cnt=ans=0;
    		tarjan(1,0);
    		for(int i=1;i<=n;i++) if(vis[i]) ans++;
    		cout<<ans<<endl;
    	}
    	
    }
    

    Kruskal

    #include <iostream>
    #include <algorithm>
    #include <iomanip>
    using namespace std;
    
    struct edge{int u,v;double w;}g[1000007];
    int n,m=1,cnt;
    int f[1000007];
    double s,ans;
    int getf(int x){
    	if(f[x]==x) return x;
    	return f[x]=getf(f[x]);
    }
    void init(){
    	for(int i=1;i<=n;i++){
    		f[i]=i;
    	}
    }
    bool cmp(edge a,edge b){
    	return a.w<b.w;
    }
    int main(){
    	cin>>s>>n;
    	init();
    	while(cin>>g[m].u>>g[m].v>>g[m].w) m++;
    	sort(g+1,g+m+1,cmp);
    	for(int i=1;i<=m;i++){
    		int x=getf(g[i].u);
    		int y=getf(g[i].v);
    		if(x==y) continue;
    		f[x]=y;
    		ans+=g[i].w;
    		cnt++;
    	}
    	if(ans<=s&&cnt==n-1) cout<<"Need "<<fixed<<setprecision(2)<<ans<<" miles of cable\n";
    	else cout<<"Impossible\n";
    	return 0;
    }
    

    树状数组

    #include <iostream>
    using namespace std;
    
    int n,m,b,l,r,tr[1000007];
    char ch;
    int lowbit(int x){return x&-x;}
    int ask(int a){
    	int ans=0;
    	while(a>0){
    		ans=ans+tr[a];
    		a=a-lowbit(a);
    	}
    	return ans;
    }
    void upd(int a,int x){
    	while(a<=n){
    		tr[a]=tr[a]+x;
    		a=a+lowbit(a);
    	}
    }
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=m;i++){
    		cin>>ch;
    		if(ch=='Q'){
    			cin>>b;
    			cout<<ask(b)<<endl;
    		}
    		if(ch=='C'){
    			cin>>l>>r;
    			upd(l,1);
    			upd(r+1,-1);
    		}
    	}
    	return 0;
    }
    

    线段树(区间查询,区间修改)

    #include <iostream>
    #define int long long
    #define func(a,b) a+b
    #define E 0
    using namespace std;
    
    struct node{
    	int lb,ub;
    	int data;
    	int tag;
    }tr[4*10000007];
    int n,m,p,x,y,s,d[10000007];
    void build(int k,int a,int b){
    	tr[k].lb=a;tr[k].ub=b;tr[k].tag=E;
    	if(a==b){
    		tr[k].data=d[a];
    		return;
    	}
    	int mid=tr[k].lb+tr[k].ub>>1;
    	build(k<<1,a,mid);
    	build(k<<1|1,mid+1,b);
    	tr[k].data=func(tr[k<<1].data,tr[k<<1|1].data);
    }
    void dtag(int k,int ls,int rs){
    	tr[k<<1].tag+=tr[k].tag;
    	tr[k<<1|1].tag+=tr[k].tag;
    	tr[k<<1].data+=tr[k].tag*(ls);
    	tr[k<<1|1].data+=tr[k].tag*(rs);
    	tr[k].tag=E;
    }
    void upd(int k,int x,int a,int b){
    	if(tr[k].lb>=a&&tr[k].ub<=b){
    		tr[k].data+=(tr[k].ub-tr[k].lb+1)*x;
    		tr[k].tag+=x;
    		return;
    	}
    	int mid=tr[k].lb+tr[k].ub>>1;
    	dtag(k,mid-tr[k].lb+1,tr[k].ub-mid);
    	if(a<=mid) upd(k<<1,x,a,b);
    	if(b>mid) upd(k<<1|1,x,a,b);
    	tr[k].data=func(tr[k<<1].data,tr[k<<1|1].data);
    }
    int query(int k,int a,int b){
    	if(tr[k].lb>=a&&tr[k].ub<=b){
    		return tr[k].data;
    	}
    	int mid=tr[k].lb+tr[k].ub>>1;
    	dtag(k,mid-tr[k].lb+1,tr[k].ub-mid);
    	int ans=E;
    	if(a<=mid) ans=func(ans,query(k<<1,a,b));
    	if(b>mid) ans=func(ans,query(k<<1|1,a,b));
    	return ans;
    }
    signed main(){
    	cin>>n;
    	cin>>m;
    	for(int i=1;i<=n;i++){
    		cin>>d[i];
    	}
    	build(1,1,n);
    	for(int i=1;i<=m;i++){
    		cin>>p>>x>>y;
    		if(p==1){
    			cin>>s;
    			upd(1,s,x,y);
    		}
    		if(p==2){
    			cout<<query(1,x,y)<<"\n";
    		}
    	}
    	return 0;
    }
    

    LCA(倍增法)

    #include <cstdio>
    #include <vector>
    #include <cmath>
    #define int long long
    using namespace std;
    
    int k=27;
    int n,m,x,y,root,f[40007][30],d[40007];
    vector<int> g[40007];
    void dfs(int u,int fa){
    	for(int i=0;i<g[u].size();i++){
    		int v=g[u][i];
    		if(v==fa) continue;
    		f[v][0]=u;
    		for(int j=1;j<=k;j++) f[v][j]=f[f[v][j-1]][j-1];
    		d[v]=d[u]+1;
    		dfs(v,u);
    	}
    }
    int lca(int x,int y){
    	if(d[x]<=d[y]) swap(x,y);
    	for(int i=k;i>=0;i--)
    		if(d[f[x][i]]>=d[y]) x=f[x][i];
    	if(x==y) return x;
    	for(int i=k;i>=0;i--)
    		if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    	return f[x][0];
    }
    signed main(){
    	scanf("%lld",&n);
    	for(int i=1;i<=n;i++){
    		scanf("%lld%lld",&x,&y);
    		if(y==-1){
    			root=x;
    		}else{
    			g[x].push_back(y);
    			g[y].push_back(x);
    		}
    	}
    	d[root]=1;
    	dfs(root,0);
    	scanf("%lld",&m);
    	for(int i=1;i<=m;i++){
    		scanf("%lld%lld",&x,&y);
    		int a=lca(x,y);
    		if(a==x) printf("%lld\n",1);
    		else if(a==y) printf("%lld\n",2);
    		else printf("%lld\n",0);
     	}
    	return 0;
    }
    

    欧拉筛

    #include <cstdio>
    #include <cstring>
    #define int long long
    using namespace std;
    
    int n,m=0,p[10000007];
    bool v[10000007];
    void init(){
    	for(int i=2;i<=n;i++){
    		if(!v[i]){
    			m=m+1;
    			p[m]=i;
    		}
    		for(int j=1;j<=m;j++){
    			if(p[j]*i>n) break;
    			v[p[j]*i]=true;
    			if(i%p[j]==0) break;
    		}
    	}
    }
    signed main(){
    	scanf("%lld",&n);
    	memset(v,false,sizeof v);
    	init();
    	printf("%lld",m);
    	return 0;
    }
    

    欧拉函数

    #include <iostream>
    #define int long long
    using namespace std;
    
    int n,m,ans,phi,ans2;
    signed main(){
    	scanf("%lld",&n);
    	m=phi=n;
    	for(int i=2;i*i<=n;i++){
    		if(n%i==0){
    			phi=phi/i*(i-1);
    			while(n%i==0) n=n/i;
    		}
    	}
    	if(n>1) phi=phi/n*(n-1);
    	for(int i=1;i*i<=m;i++){
    		if(m%i==0){
    			ans++;
    			if(i*i!=m) ans++;
    		}
    	}
    	printf("%lld",m-phi-ans+1);
    	return 0;
    }
    

    exgcd

    #include <cstdio>
    #define int long long
    using namespace std;
    
    void swap(int &a,int &b){
    	int tmp=a;
    	a=b;
    	b=tmp;
    }
    int exgcd(int a,int b,int &x,int &y){
    	if(b==0){
    		x=1,y=0;
    		return a;
    	}
    	int d=exgcd(b,a%b,x,y);
    	int tmp=x;
    	x=y;
    	y=tmp-a/b*y;
    	return d;
    }
    int x,y,m,o,l,e,f,a,b,n;
    signed main(){
    	scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&o,&l);
    	a=o-m;
    	b=l;
    	n=x-y;
    	if(a<0) a=-a,n=-n;
    	int g=exgcd(a,b,e,f);
    	if(n%g!=0){
    		printf("Impossible\n");
    		return 0;
    	}
    	int z=b/g;
    	printf("%lld\n",(e*n/g%z+z)%z);
    }
    

    改天整理一下。。。