|
文件读入读出 假设题目名为“add”，那么文件夹名为“add”，c++程序名为“add.cpp”，读入文件名为“add.in”，输出文件名为“add.out”。四个的拼写均不可有误，包括大小写差异。千万不要调试后就忘记修改文件读入读出了。 #include int main(){ freopen('add.in','r',stdin);//read freopen('add.out','w',stdout);//write } 数论算法 1、线性筛 #include #include #include #include using namespace std; const int maxn=200005; int prime[maxn]; bool not_prime[maxn]; int main() { int n,cnt=0; scanf('%d',&n); memset(not_prime,0,sizeof(not_prime)); not_prime[1]=true; for(inti=2;i<> { if(!not_prime[i]) prime[++cnt]=i; for(intj=1;j<> { if(prime[j]*i>n) break; not_prime[prime[j]*i]=true; if(i%prime[j]==0) break; } } for(inti=1;i<> printf('%d ',prime[i]); return 0; }
2、埃氏筛 #include #include #include #include using namespace std; inline int read() { char c; c=getchar(); for(;c>'9'||c<> int sum=0; for(;c<='9'&&c>='0';c=getchar())sum=sum*10+c-48; return sum; } int n,m; bool f[10010000]; int main() { n=read(),m=read(); memset(f,true,sizeof(f)); f[0]=f[1]=false; for(inti=2;i<> if(f[i]) for(intj=2;i*j<> for(inti=1;i<> { int x; x=read(); if(f[x])printf('Yes\n'); elseprintf('No\n'); } return 0; }
3、拓展欧几里得算法 #include #include #include #include using namespace std; int x,y; int exgcd(int a,int b) { if(!b) { x=1; y=0; return a; } else { int t; intd=exgcd(b,a%b); t=x; x=y; y=t-a/b*x; return d; } } int main() { int a,b; scanf('%d%d',&a,&b); exgcd(a,b); // cout<><> cout<><'><><> return 0; }
4、GCD&LCM #include #include #include using namespace std; int gcd(int a,int b) { if(!b) returna; else returngcd(b,a%b); } int lcm(int a,int b) { returna/gcd(a,b)*b; } int main() { int a,b; scanf('%d%d',&a,&b); cout<><'><><> return 0; }
5、分解质因数 #include #include #include using namespace std; int main() { long long n; scanf('%lld',&n); for(long longi=2;i<> { while(n!=i) { if(n%i==0) { printf('%lld*',i); n=n/i; } elsebreak; } } printf('%lld',n); return 0; }
6、大数翻倍法 #include #include #include using namespace std; int a[233],mo[233]; int gcd(int a,int b) { if(!b) returna; else returngcd(b,a%b); } int lcm(int a,int b) { returna/gcd(a,b)*b; } int main() { int n; scanf('%d',&n); for(inti=1;i<> scanf('%d%d',&a[i],&mo[i]); intans=0,nowmo=1; for(inti=1;i<> { intother=a[i],othermo=mo[i]; if(othermo>nowmo) { swap(ans,other); swap(nowmo,othermo); } while(ans%othermo!=other) ans+=nowmo; nowmo=lcm(nowmo,othermo); } printf('%d',ans); }
7、快速幂 #include using namespace std; const int MOD = 1007; int xx(int a,int n,int MOD) { int ret=1; int tmp=a%MOD; while(n) { if(n&1) ret=ret*tmp%MOD; tmp=tmp*tmp%MOD; n>>=1; } return ret; } int main() { int m,n; while(scanf('%d%d',&m,&n)==2) { printf('%d\n',xx(m,n,MOD)); } }
8、位运算
长沙信息学竞赛 |
|
|
