自己收集整理的一些模板= - (毕业了就整理一下
……
……
……
*your soul will be so sweet*
const int Mx=1252,MOD=100000000; struct BIGN{ int a[Mx+10]; BIGN(){memset(a,0,sizeof a);} int &operator [](int i){return a[i];} inline void operator /=(int x){ for(int i=Mx;i>=1;--i) a[i-1]+=a[i]%x*MOD,a[i]/=x; } inline void operator -=(BIGN &b){ for(int i=1;i<Mx;++i) a[i]=a[i]-b[i]+(a[i-1]+MOD)/MOD -1,a[i-1]=(a[i-1]+MOD)%MOD; } inline void operator +=(BIGN &b){ Mx; for(int i=1;i<=Mx;++i)a[i]+=b[i]; for(int i=1;i<=Mx;++i)if(a[i]>=MOD)++a[i+1],a[i]%=MOD; } inline void operator *=(int x){ for(int i=1;i<Mx;++i) a[i]=a[i]*x+a[i-1]/MOD,a[i-1]%=MOD; } inline bool operator <(BIGN &b){ for(int i=Mx;i>=1;--i) if(a[i]!=b[i]) return a[i]<b[i]; return false; } inline bool iszero(){ for(int i=1;i<Mx;++i)if(a[i]!=0)return false; return true; } inline void read(){ char tp[10005]={'0','0','0','0','0','0','0','0'}; scanf("%s",tp+8); int len=strlen(tp+1),p=1; while(len-8*p+1>0) sscanf(tp+len-8*p+++1,"%8d",&a[p]); } inline void print(){ int p=Mx; while(!a[p]&&p>0) p--; printf("%d",a[p--]); while(p>0) printf("%08d",a[p--]); printf("\n"); } };
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> #define oo (1<<30) #define N 100005 #define M 1000005 int n,S,T,ll,son[N],d[N],q[N],link[M],next[M],cap[M],opp[M]; inline int min(int x,int y){return x<y?x:y;} bool build(){ int x,y,l=1,r=1; memset(d,-1,sizeof(int)*(n+5)); q[1]=S;d[S]=0; while(l<=r){ x=q[l++]; for(int i=son[x];i!=-1;i=next[i]){ y=link[i]; if(cap[i]&&d[y]==-1){ d[y]=d[x]+1;q[++r]=y; if(y==T)return 1; } } } return 0; } int find(int now,int flow){ int ret,y,w=0; if(now==T)return flow; for(int i=son[now];i!=-1&&w<flow;i=next[i]){ y=link[i]; if(cap[i]&&d[y]==d[now]+1&&(ret=find(y,min(flow-w,cap[i])))) cap[i]-=ret,cap[opp[i]]+=ret,w+=ret; } if(!w)d[now]=-1; return w; } void addedge(int x,int y,int z){ link[++ll]=y;next[ll]=son[x];son[x]=ll;cap[ll]=z;opp[ll]=ll+1; link[++ll]=x;next[ll]=son[y];son[y]=ll;cap[ll]=0;opp[ll]=ll-1; } int main(){ int m,x,y,z,ans,flow; //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); while(~scanf("%d%d",&m,&n)){ memset(son,-1,sizeof(int)*(n+5)); S=1;T=n;ans=0;ll=0; for(int i=1;i<=m;++i) scanf("%d%d%d",&x,&y,&z),addedge(x,y,z); while(build()) while(1){ flow=find(S,oo); if(!flow)break; ans+=flow; } printf("%d\n",ans); } }
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> #include<math.h> #include<iostream> #include<algorithm> using namespace std; namespace fastIO{ #define BUF_SIZE 100000 #define OUT_SIZE 100000 #define ll long long //fread->read bool IOerror=0; inline char nc(){ static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; if (p1==pend){ p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); if (pend==p1){IOerror=1;return -1;} //{printf("IO error!\n");system("pause");for (;;);exit(0);} } return *p1++; } inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} inline void read(int &x){ bool sign=0; char ch=nc(); x=0; for (;blank(ch);ch=nc()); if (IOerror)return; if (ch=='-')sign=1,ch=nc(); for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; if (sign)x=-x; } inline void read(ll &x){ bool sign=0; char ch=nc(); x=0; for (;blank(ch);ch=nc()); if (IOerror)return; if (ch=='-')sign=1,ch=nc(); for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; if (sign)x=-x; } inline void read(double &x){ bool sign=0; char ch=nc(); x=0; for (;blank(ch);ch=nc()); if (IOerror)return; if (ch=='-')sign=1,ch=nc(); for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; if (ch=='.'){ double tmp=1; ch=nc(); for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0'); } if (sign)x=-x; } inline void read(char *s){ char ch=nc(); for (;blank(ch);ch=nc()); if (IOerror)return; for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch; *s=0; } inline void read(char &c){ for (c=nc();blank(c);c=nc()); if (IOerror){c=-1;return;} } //getchar->read inline void read1(int &x){ char ch;int bo=0;x=0; for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); if (bo)x=-x; } inline void read1(ll &x){ char ch;int bo=0;x=0; for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); if (bo)x=-x; } inline void read1(double &x){ char ch;int bo=0;x=0; for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); if (ch=='.'){ double tmp=1; for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar()); } if (bo)x=-x; } inline void read1(char *s){ char ch=getchar(); for (;blank(ch);ch=getchar()); for (;!blank(ch);ch=getchar())*s++=ch; *s=0; } inline void read1(char &c){for (c=getchar();blank(c);c=getchar());} //scanf->read inline void read2(int &x){scanf("%d",&x);} inline void read2(ll &x){ #ifdef _WIN32 scanf("%I64d",&x); #else #ifdef __linux scanf("%lld",&x); #else puts("error:can't recognize the system!"); #endif #endif } inline void read2(double &x){scanf("%lf",&x);} inline void read2(char *s){scanf("%s",s);} inline void read2(char &c){scanf(" %c",&c);} inline void readln2(char *s){gets(s);} //fwrite->write struct Ostream_fwrite{ char *buf,*p1,*pend; Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;} void out(char ch){ if (p1==pend){ fwrite(buf,1,BUF_SIZE,stdout);p1=buf; } *p1++=ch; } void print(int x){ static char s[15],*s1;s1=s; if (!x)*s1++='0';if (x<0)out('-'),x=-x; while(x)*s1++=x%10+'0',x/=10; while(s1--!=s)out(*s1); } void println(int x){ static char s[15],*s1;s1=s; if (!x)*s1++='0';if (x<0)out('-'),x=-x; while(x)*s1++=x%10+'0',x/=10; while(s1--!=s)out(*s1); out('\n'); } void print(ll x){ static char s[25],*s1;s1=s; if (!x)*s1++='0';if (x<0)out('-'),x=-x; while(x)*s1++=x%10+'0',x/=10; while(s1--!=s)out(*s1); } void println(ll x){ static char s[25],*s1;s1=s; if (!x)*s1++='0';if (x<0)out('-'),x=-x; while(x)*s1++=x%10+'0',x/=10; while(s1--!=s)out(*s1); out('\n'); } void print(double x,int y){ static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000, 1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL, 100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL}; if (x<-1e-12)out('-'),x=-x;x*=mul[y]; ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1; ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2); if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);} } void println(double x,int y){print(x,y);out('\n');} void print(char *s){while (*s)out(*s++);} void println(char *s){while (*s)out(*s++);out('\n');} void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}} ~Ostream_fwrite(){flush();} }Ostream; inline void print(int x){Ostream.print(x);} inline void println(int x){Ostream.println(x);} inline void print(char x){Ostream.out(x);} inline void println(char x){Ostream.out(x);Ostream.out('\n');} inline void print(ll x){Ostream.print(x);} inline void println(ll x){Ostream.println(x);} inline void print(double x,int y){Ostream.print(x,y);} inline void println(double x,int y){Ostream.println(x,y);} inline void print(char *s){Ostream.print(s);} inline void println(char *s){Ostream.println(s);} inline void println(){Ostream.out('\n');} inline void flush(){Ostream.flush();} //puts->write char Out[OUT_SIZE],*o=Out; inline void print1(int x){ static char buf[15]; char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x; while(x)*p1++=x%10+'0',x/=10; while(p1--!=buf)*o++=*p1; } inline void println1(int x){print1(x);*o++='\n';} inline void print1(ll x){ static char buf[25]; char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x; while(x)*p1++=x%10+'0',x/=10; while(p1--!=buf)*o++=*p1; } inline void println1(ll x){print1(x);*o++='\n';} inline void print1(char c){*o++=c;} inline void println1(char c){*o++=c;*o++='\n';} inline void print1(char *s){while (*s)*o++=*s++;} inline void println1(char *s){print1(s);*o++='\n';} inline void println1(){*o++='\n';} inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}} struct puts_write{ ~puts_write(){flush1();} }_puts; inline void print2(int x){printf("%d",x);} inline void println2(int x){printf("%d\n",x);} inline void print2(char x){printf("%c",x);} inline void println2(char x){printf("%c\n",x);} inline void print2(ll x){ #ifdef _WIN32 printf("%I64d",x); #else #ifdef __linux printf("%lld",x); #else puts("error:can't recognize the system!"); #endif #endif } inline void println2(ll x){print2(x);printf("\n");} inline void println2(){printf("\n");} #undef ll #undef OUT_SIZE #undef BUF_SIZE }; using namespace fastIO; int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); int n,x,sum=0;long long lx;char str[105],ch; println(3.01,2);flush(); print(-1);print(' '); println2(123456789123456789LL); println(-3.141592653589,10); println(2.9999,2); read2(ch);println2(ch); read1(lx);println(lx); read(n); for (int i=1;i<=n;++i)read(x),sum+=x; printf("%d\n",sum); read(str); puts(str); print1("zzy dhh"); println("zhazha frog"); flush1(); flush(); system("pause");for (;;); return 0; } /* input: A 123456789123456789 3 1 10 100 nie&&ga! output: 3.01 123456789123456789 A 111 nie&&ga! zzy dhh -1 -3.1415926536 3.00 123456789123456789 zhazha frog */
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> #include<math.h> #include<iostream> #include<algorithm> using namespace std; namespace fastIO{ #define BUF_SIZE 100000 //fread->read bool IOerror=0; inline char nc(){ static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE; if (p1==pend){ p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin); if (pend==p1){IOerror=1;return -1;} //{printf("IO error!\n");system("pause");for (;;);exit(0);} } return *p1++; } inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} inline void read(int &x){ bool sign=0; char ch=nc(); x=0; for (;blank(ch);ch=nc()); if (IOerror)return; if (ch=='-')sign=1,ch=nc(); for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; if (sign)x=-x; } inline void read(double &x){ bool sign=0; char ch=nc(); x=0; for (;blank(ch);ch=nc()); if (IOerror)return; if (ch=='-')sign=1,ch=nc(); for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; if (ch=='.'){ double tmp=1; ch=nc(); for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0'); } if (sign)x=-x; } inline void read(char *s){ char ch=nc(); for (;blank(ch);ch=nc()); if (IOerror)return; for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch; *s=0; } //getchar->read inline void read1(int &x){ char ch;int bo=0;x=0; for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); if (bo)x=-x; } inline void read1(double &x){ char ch;int bo=0;x=0; for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1; for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar()); if (ch=='.'){ double tmp=1; for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar()); } if (bo)x=-x; } void read1(char *s){ char ch=getchar(); for (;blank(ch);ch=getchar()); for (;!blank(ch);ch=getchar())*s++=ch; *s=0; } //scanf->read void read2(int &x){scanf("%d",&x);} void read2(double &x){scanf("%lf",&x);} void read2(char *s){scanf("%s",s);} //fwrite->write struct Ostream_fwrite{ char *buf,*p1,*pend; Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;} void out(char ch){ if (p1==pend){ fwrite(buf,1,BUF_SIZE,stdout);p1=buf; } *p1++=ch; } void print(int x){ static char s[15],*s1;s1=s; if (!x)*s1++='0';if (x<0)*s1++='-',x=-x; while(x)*s1++=x%10+'0',x/=10; while(s1--!=s)out(*s1); out('\n'); } void print(char *s){ while (*s)out(*s++);out('\n'); } void flush(){ if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;} } ~Ostream_fwrite(){flush();} }Ostream; inline void print(int x){Ostream.print(x);} inline void print(char *s){Ostream.print(s);} inline void flush(){Ostream.flush();} //puts->write char Out[BUF_SIZE],*o=Out; inline void print1(int x){ static char buf[15]; char *p1=buf;if (!x)*p1++='0';if (x<0)*p1++='-',x=-x; while(x)*p1++=x%10+'0',x/=10; while(p1--!=buf)*o++=*p1; *o++='\n'; } inline void print1(char *s){ while (*s)*o++=*s++; *o++='\n'; } inline void flush1(){if (o!=Out)*--o=0;puts(Out);} #undef BUF_SIZE }; using namespace fastIO; int main(){ freopen("1.in","r",stdin); freopen("fastIO_fread.out","w",stdout); int t1=clock(); int n,x;read(n); for (int i=1;i<=n;++i)read(x); printf("time=%d\n",clock()-t1); fclose(stdin);fclose(stdout); freopen("1.in","w",stdout); srand(time(0));t1=clock(); n=10000000;printf("%d\n",n); for (int i=1;i<=n;++i)print(rand()*rand()); flush(); fclose(stdout); freopen("fastIO_fwrite.out","w",stdout); printf("time=%d\n",clock()-t1); fclose(stdout); //system("pause");for (;;); return 0; }
//v1.5.0→v2.0.0 大大缩短代码but大幅度增加内存&提升速度 //v2.0.0→v2.1.0 提升速度 namespace Read{ const int S=5000000; char _str[S],*p=_str; inline int read(){ int x=0;for(;*p<'0'||*p>'9';++p); while(*p>='0'&&*p<='9')x=x*10+*p++-48; return x; } } using Read::read; char buf[10],out[6000005],*o=out; inline void print(int x){ char *b=buf;if (!x)*b++='0'; while(x){*b++=x%10+48;x/=10;} while(b--!=buf)*o++=*b; *o++='\n'; } //处理负数 namespace Read{ const int S=5000000; char _str[S],*p=_str; inline void read(int &x){ bool f; x=0;for(;(*p<'0'||*p>'9')&&(*p!='-');p++); if(*p=='-')f=true,++p;else f=false; while(*p>='0'&&*p<='9')x=x*10+*p++-48; if(f)x=-x; } } using Read::read; char buf[10],out[6000005],*o=out; inline void print(int x){ char *b=buf;if (!x)*b++='0'; if(x<0){*o++='-';x=-x;} while(x){*b++=x%10+48;x/=10;} while(b--!=buf)*o++=*b; *o++='\n'; } fread(Read::p,1,Read::S,stdin); puts(out);
//v2.1.0→v3.0.0 内存大大减小,代码增长一倍,速度稍微变慢 //v3.0.0→v3.4.0 内存减小到固定100k 代码进行优化 //v3.4.0→v3.5.5 代码优化 //v3.5.5→v3.6.0 增添补丁、输出优化(小内存) //v3.6.0→v3.7.2 提升速度,优化代码 //v3.7.2→v3.7.6 增添简洁版 namespace fastIO{ #define S 100000 bool IOerror=0; inline char nc(){ static char buf[S],*p1=buf+S,*pend=buf+S; if(p1==pend){p1=buf;pend=buf+fread(buf,1,S,stdin);if(pend==p1)return IOerror=1,-1;} return *p1++; } inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';} inline int read(){ char ch=nc();int x=0;for(;blank(ch);ch=nc()); if(IOerror)return -1;for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; return x; } #undef S }; using namespace fastIO; //简洁版(不适用补丁) #define S 100000 inline char nc(){ static char buf[S],*p1=buf+S,*pend=buf+S; if(p1==pend){p1=buf;pend=buf+fread(buf,1,S,stdin);if(pend==p1)return-1;} return *p1++; } inline int read(){ char ch=nc();int x=0;for(;ch<'0'||ch>'9';ch=nc()); for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';return x; } //输出优化(补丁): struct Fast_print{ char *buf,*p1,*pend; Fast_print(){buf=new char[S];p1=buf;pend=buf+S;} inline void out(char ch){if(p1==pend)fwrite(buf,1,S,stdout),p1=buf;*p1++=ch;} inline void print(int x){ static char s[15],*s1;s1=s;if(!x)*s1++='0';if(x<0)*s1++='-',x=-x; while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);//out('\n'); } void flush(){if(p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}} ~Fast_print(){flush();} }so_Fast; inline void print(int x){so_Fast.print(x);} //补丁 inline int read(){ bool sign=0;char ch=nc();int x=0;for(;blank(ch);ch=nc()); if(IOerror)return -1;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; if(sign)x=-x;return x; } inline void read(double &x){ bool sign=0;char ch=nc();x=0; for(;blank(ch);ch=nc()); if(IOerror)return; if(ch=='-')sign=1,ch=nc(); for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; if(ch=='.'){ double tmp=1;ch=nc(); for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0'); } if(sign)x=-x; } inline void read(char *s){ char ch=nc(); for(;blank(ch);ch=nc()); if(IOerror)return; for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch; *s=0; } inline void read(char &c){ for(c=nc();blank(c);c=nc()); if(IOerror){c=-1;return;} } #define ll long long inline void read(ll &x){ bool sign=0;char ch=nc();x=0; for(;blank(ch);ch=nc()); if(IOerror)return; if(ch=='-')sign=1,ch=nc(); for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0'; if(sign)x=-x; }
//力 #include<cstring> #include<algorithm> #include<cstdio> #include<complex> #include<cmath> #define pi 3.141592653589793238462643383 using namespace std; typedef complex<double>E; E f[300003],_f[300003],g[300003],e1[300003],e2[300003]; int n,L,m,rev[300003]; inline void fft(E *a,int f){ for(int i=0;i<n;++i)if(i>rev[i])swap(a[i],a[rev[i]]); for(int i=1;i<n;i<<=1){ E wn(cos(pi/i),f*sin(pi/i)); for(int j=0;j<n;j+=(i<<1)){ E w(1,0); for(int k=0;k<i;++k,w*=wn){ E x=a[j+k],y=w*a[j+k+i]; a[j+k]=x+y,a[j+k+i]=x-y; } } } if(f==-1)for(int i=0;i<n;++i)a[i]/=n; } int main(){ scanf("%d",&n);--n; for(int i=0;i<=n;++i){ double x;scanf("%lf",&x); f[i]=x,_f[n-i]=x; } m=2*n;for(n=1;n<=m;n<<=1)++L; for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1)); for(int i=1;i<=n;++i)g[i]=(1.0/i/i); fft(f,1),fft(_f,1),fft(g,1); for(int i=0;i<n;++i)e1[i]=f[i]*g[i]; for(int i=0;i<n;++i)e2[i]=_f[i]*g[i]; fft(e1,-1),fft(e2,-1); for(int i=0;i<=m/2;++i)printf("%.3lf\n",e1[i].real()-e2[m/2-i].real()); }
#include<bits/stdc++.h> using namespace std; #define ll long long ll quickpow(ll m,ll n,ll k){int b=1;while(n>0){if(n&1)b=(b*m)%k;n=n>>1;m=(m*m)%k;}return b;} inline ll read(){ char ch;ll a=0;bool f=false; ch=getchar();while((ch<'0'||ch>'9')&&(ch!='-'))ch=getchar(); if(ch!='-')a*=10,a+=ch-'0';else f=true; while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0'; if(f)a=-a;return a; } void gcd(ll a,ll b,ll &d,ll &x,ll &y){ if(!b)d=a,x=1,y=0; else gcd(b,a%b,d,y,x),y-=x*(a/b); } inline ll mul_mod(ll a,ll b,ll n){return a*b%n;} inline ll inv(ll a,ll n){ ll d,x,y; gcd(a,n,d,x,y); return d==1?(x+n)%n:-1; } inline ll log_mod(ll a,ll b,ll n){ ll m=(ll)sqrt(n+0.5),v=inv(quickpow(a,m,n),n),e=1,i; map<int,int>x; x[1]=0; for(i=1;i<m;++i){ e=mul_mod(e,a,n); if(!x.count(e))x[e]=i; } for(i=0;i<m;i++){ if(x.count(b))return i*m+x[b]; b=mul_mod(b,v,n); } return -1; } int main(){ freopen("calc.in","r",stdin); freopen("calc.out","w",stdout); int T=read(),Q=read(); while(T--){ ll a=read(),b=read(),p=read(); if(Q==1)printf("%lld\n",quickpow(a,b,p)); else if(Q==2){ ll x=quickpow(a,p-2,p)*b%p; if(x*a%p==b%p)printf("%lld\n",x); else puts("Orz, I cannot find x!"); }else{ ll x=log_mod(a,b,p); if(x==-1)puts("Orz, I cannot find x!"); else printf("%lld\n",x); } } }
void rmq_init(){ int i,j,t; for(j=1;j<=n;j++)mx[j][0]=mn[j][0]=h[j]; int m=floor(log((double)n)/log(2.0)); for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ t=j+(1<<(i-1)); if(t<=n)mx[j][i]=max(mx[j][i-1],mx[t][i-1]); else mx[j][i]=mx[j][i-1]; } } for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ t=j+(1<<(i-1)); if(t<=n)mn[j][i]=min(mn[j][i-1],mn[t][i-1]); else mn[j][i]=mn[j][i-1]; } } } int rmq(int l,int r){ int m=floor(log((double)(r-l+1))/log(2.0)); int a=max(mx[l][m],mx[r-(1<<m)+1][m]); int b=min(mn[l][m],mn[r-(1<<m)+1][m]); return a-b; }
void tarjan(int x){ low[x]=dfn[x]=++dfs_clock; inq[x]=1,q[++top]=x; for(int i=last[x];i;i=e[i].next) if(!dfn[e[i].to])tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]); else if(inq[e[i].to])low[x]=min(low[x],dfn[e[i].to]); if(low[x]==dfn[x]){ int now=0;++scc; for(;x!=now;now=q[top],--top,bl[now]=scc,inq[now]=0,++num[scc]); } }
/* ID:hqztrue1 LANG:C++ TASK:ditch */ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> const int maxn=20010; const int maxm=500010; #define oo 50000000 int son[maxn],q[maxn],d[maxn],pre[maxn]; int link[maxm],st[maxm],next[maxm],cap[maxm],opp[maxm],cost[maxm]; int n,m,i,S,T,ll,ans,maxflow,mincost; int x,y,z; void addedge(int x,int y,int z,int c){ link[++ll]=y;st[ll]=x;next[ll]=son[x];son[x]=ll;cap[ll]=z;cost[ll]=c;opp[ll]=ll+1; link[++ll]=x;st[ll]=y;next[ll]=son[y];son[y]=ll;cap[ll]=0;cost[ll]=-c;opp[ll]=ll-1; } int spfa(int s){ int h=1,t=1,i,j,p; memset(d,6,sizeof(int)*(n+5)); d[S]=0;q[1]=S; while (h<=t){ i=q[h++]; for(p=son[i];p!=-1;p=next[p]){ j=link[p]; if(d[i]+cost[p]<d[j]&&cap[p]){ d[j]=d[i]+cost[p]; pre[j]=p;q[++t]=j; } } } return d[T]>oo?0:1; } void update(){ int p,flow=oo; for(p=T;p!=S;p=st[p]){ p=pre[p];if(cap[p]<flow)flow=cap[p]; } maxflow+=flow; for(p=T;p!=S;p=st[p]){ p=pre[p];mincost+=cost[p]*flow; cap[p]-=flow;cap[opp[p]]+=flow; } } int main(){ //srand(time(0)); freopen("ditch.in","r",stdin); freopen("ditch.out","w",stdout); ll=0;scanf("%d%d",&m,&n); memset(son,-1,sizeof(int)*(n+5)); S=1;T=n;maxflow=mincost=0; for (i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); addedge(x,y,z,rand()&32767); } while (spfa(S))update(); printf("%d\n",maxflow); //printf("%d\n",mincost); //system("pause"); return 0; }
//by Rxd //height void Get_Height(){ int k=0; for(int i=0;i<n;i++){ if(k)k--; int j=SA[x[i]-1]; while(s[i+k]==s[j+k])k++; Height[x[i]]=k; } } //SA void Build_SA(){ memset(c,0,sizeof(c)); for(int i=0;i<n;i++)c[x[i]=s[i]]++; for(int i=1;i<m;i++)c[i]+=c[i-1]; for(int i=n-1;i>=0;i--)SA[--c[x[i]]]=i; for(int k=1;k<=n;k<<=1){ int cnt=0; for(int i=n-k;i<n;i++)y[cnt++]=i; for(int i=0;i<n;i++) if(SA[i]>=k)y[cnt++]=SA[i]-k; memset(c,0,sizeof(c)); for(int i=0;i<n;i++)c[x[y[i]]]++; for(int i=1;i<m;i++)c[i]+=c[i-1]; for(int i=n-1;i>=0;i--)SA[--c[x[y[i]]]]=y[i]; swap(x,y); cnt=1;x[SA[0]]=0; for(int i=1;i<n;i++) x[SA[i]]=(y[SA[i-1]]==y[SA[i]]&&y[SA[i-1]+k]==y[SA[i]+k]?cnt-1:cnt++); if(cnt>=n)break; m=cnt; } }
/*#include<cstdio> using namespace std; int a[300][300],b[300][300],c[300][300]; int main(){ int n,m,p; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); scanf("%d%d",&m,&p); for(int i=1;i<=m;i++) for(int j=1;j<=p;j++) scanf("%d",&b[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=p;j++) for(int k=1;k<=m;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; for(int i=1;i<=n;i++) for(int j=1;j<=p;j++) if(j==p)printf("%d\n",c[i][j]); else printf("%d ",c[i][j]); }*/ #include<cstring> #include<cstdio> #include<algorithm> const int p=10000; using namespace std; struct node{ long long k[3][3]; }m,tt; node ju(node a,node b){ node c; memset(c.k,0,sizeof(c.k)); for(int i=1;i<=2;i++) for(int j=1;j<=2;j++){ c.k[i][j]=0; for(int k=1;k<=2;k++){ c.k[i][j]+=(a.k[i][k]*b.k[k][j])%p; c.k[i][j]=c.k[i][j]%p; } } return c; } int main(){ while(1){ int n; scanf("%d",&n); if(n==-1)break; if(n==0){ printf("0\n"); continue; } n-=1; tt.k[1][2]=1; tt.k[1][1]=tt.k[2][1]=tt.k[2][2]=0; m.k[1][1]=0; m.k[1][2]=m.k[2][1]=m.k[2][2]=1; while(n>0){ if(n&1)tt=ju(tt,m); n=n>>1; m=ju(m,m); } printf("%d\n",tt.k[1][2]); } } /*int quickpow(int m,int n,int k){ int b=1; while(n>0){ if(n&1)b=(b*m)%k; n=n>>1; m=(m*m)%k; } return b; }*/
int sum(int x){ int ret=0; while(x>0)ret+=c[x],x-=lowbit(x); return ret; } void add(int x,int d){ while(x<=n)c[x]+=d,x+=lowbit(x); }
loading...