文章目录

基础数学算法分解质因子欧几里得|辗转相除数字分离倒序输出数字分离求数字和判断素数素数筛法回文数快速幂 PracticeT1 SeperateT2 PaimingT3 hwsT4 Circle

基础数学算法

分解质因子

直接输出

int main(){ int n=in,i=2,nn; nn=n;//必须标记，否则无法在最后一个不输出‘*’ printf("%d=",n); while(n!=1){ while(n%i==0){ if(n==nn)printf("%d",i); else printf("*%d",i); n/=i; } i++; } return 0; }

存到数组里

int main(){ int n=in,i=2,nn; int m,factor[NNN]; nn=n;//必须标记，否则无法在最后一个不输出‘*’ while(n!=1){ while(n%i==0){ factor[++m]=i; n/=i; } i++; } for(re int i=1;i<=m;i++)printf("%d ",factor[i]); return 0; }

欧几里得|辗转相除

递归实现

int gcd(int a,int b){ if(!b)return a; return gcd(b,a%b); }

循环实现

int main(){ int a=in,b=in; while(a%b!=0){ int tmp=a%b; a=b,b=tmp; } printf("%d",b); }

数字分离倒序输出

最方便的数字处理

int main(){ ll a=in; while(a){ printf("%d",a%10); a/=10; } return 0; }

数字太大超$longlong$ 莫法，只能用字符串 数组实现

int main(){ int number[NNN],m; char ch=getchar(); while(ch>='0'&&ch<='9') number[++m]=ch-48,ch=getchar(); for(re int i=m;i>=1;i--) printf("%d",number[i]); return 0; }

数字分离求数字和

当然也可以拆开一位一位地加

int main(){ ll a=in,s=0; while(a){ s+=a%10; a/=10; } printf("%d",s); return 0; }

数字超$longlong$，用字符串 注意，必须用文件操作 因为标准输入输出没法判断你输完了没有

int main(){ freopen("sumnum.in","r",stdin); freopen("sumnum.out","w",stdout); int s=0; char ch; while(cin>>ch) s+=ch-48; printf("%d",s); return 0; }

判断素数

bool prime(int x){ for(re int i=2;i<=sqrt(x);i++) if(x%i==0)return false; return true; }

素数筛法

埃氏筛法$O(Nlo{g}_2(lo{g}_{2}N))$

int n,m,prime[5000];//[1,10000]只有1229个质数 bool is_prime[NNN]; void primes(int n){ memset(is_prime,true,sizeof(is_prime)); is_prime[1]=false; for(re int i=2;i<=n;i++) if(is_prime[i]){ prime[++m]=i; int k=n/i;//技巧：少算j次 for(re int j=i;j<=k;j++) is_prime[i*j]=false; } } int main(){ n=in; primes(n); for(re int i=1;i<=m;i++) printf("%d ",prime[i]); return 0; }

谨用这个少算j次的技巧向yxt巨佬致敬！！

线性筛法$O(N)$

int n,m,prime[NNN]; bool is_prime[NNN]; void primes(int n){ memset(is_prime,true,sizeof(is_prime)); is_prime[1]=false; for(re int i=2;i<=n;i++){ if(is_prime[i])prime[++m]=i; for(re int j=1;j<=m;j++){ if(prime[j]*i>n)break;//这一步还可以用yxt巨巨的方法优化 is_prime[prime[j]*i]=false; if(!i%prime[j])break; } } } int main(){ int n=in; primes(n); for(re int i=1;i<=m;i++) printf("%d ",prime[i]); return 0; }

回文数

小数据，可以用数字分离倒序输出的方法

int main(){ ll x=0,y=0,p=1;//x正序，y倒叙，p记录y的位数 char ch; while(ch<'0'||ch>'9')ch=getchar();//边读入边生成x和y while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+ch-48; y+=p*(ch-48); p*=10; ch=getchar(); } if(x==y)printf("True"); else printf("False"); return 0; }

大数据，没办法只能用字符串 只需要比较对称的部分 对于奇数位数的数，中间的那一个数舍去

char num[NNN]; int len,n; bool v=true; int main(){ scanf("%s",num+1); n=strlen(num+1); len=n>>1; for(re int i=1;i<=len;i++) if(num[i]!=num[n-i+1]){ v=false; break; } if(v)printf("True"); else printf("False"); return 0; }

快速幂

计算$a^b$

int fastpow(int a,int b){ int ans=1; while(b){ if(b&1)ans*=a; a=a*a; b>>=1; } printf("%d",ans); return 0; }

计算$a^b(modc)$

int fastpow(int a,int b,int c){ int ans=1; while(b){ if(b&1)ans=(ans%c)*(a%c)%c; a=(a%c)*(a%c)%c; b>>=1; } return ans; }

Practice

T1 Seperate

输出一个数从右往左数第k个 Sample Input 1 2076 2 Sample Output 1 7 Sample Input 2 2076 5 Sample Output 2 0 Solution

#include<bits/stdc++.h> using namespace std; #define re register int main(){ long long n; int k; scanf("%lld%d",&n,&k); for(re int i=1;i<k;i++) n/=10; printf("%d",n%10); return 0; }

[解题报告] 对于有可能输出0的，里都不需要理它 0多除几个10还是0

T2 Paiming

Sample Input 5 300 5 200 6 350 4 400 6 250 5 Sample Output 0 0 1 1 3 Solution

#include<bits/stdc++.h> using namespace std; #define in Read() #define re register #define NNN 210 int n; struct st{ int s,g,num; }student[NNN]; inline int in{ int i=0,f=1;char ch='$'; while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-'){ ch=getchar();f=-1; } while(ch>='0'&&ch<='9')i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } inline bool comp(const st &a,const st &b){ if(a.s!=b.s)return a.s>b.s; return a.g<b.g; } int main(){ n=in; for(re int i=1;i<=n;i++) student[i].s=in,student[i].g=in; sort(student+1,student+n+1,comp); // printf("\n"); // for(re int i=1;i<=n;i++) // printf("%d %d\n",student[i].s,student[i].g); // for(re int i=1;i<=n;i++) for(re int j=1;j<=i;j++) if(student[i].g>student[j].g) student[i].num++; for(re int i=1;i<=n;i++) printf("%d\n",student[i].num); return 0; }

T3 hws

数据没多大，暴力枚举就行 Solution

#include<bits/stdc++.h> using namespace std; #define in Read() #define re register inline int in{ int i=0,f=1;char ch='$'; while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-'){ ch=getchar();f=-1; } while(ch>='0'&&ch<='9')i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } inline bool check(int x){ int a=0,b=0,p=1; while(x){ a=(a<<1)+(a<<3)+(x%10); b+=p*(x%10); x/=10; p*=10; } if(a==b)return true; else return false; } int main(){ int n=in,sum=0; for(re int i=1;i<=n;i++)sum+=check(i); printf("%d",sum); return 0; }

T4 Circle

Sample Input 10 3 4 5 Sample Output 5 一大堆废话T_T 就是让你求$(x+m\times 10^k)modn$ [数据范围]只是为了吓一吓你 Solution

#include<bits/stdc++.h> using namespace std; #define in Read() #define re register inline int in{ int i=0,f=1;char ch; while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-'){ ch=getchar();f=-1; } while(ch>='0'&&ch<='9')i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } inline int calc(int n,int m,int k,int x){ int p=10,ans=m; while(k){ if(k&1)ans=(ans%n)*(p%n); p=(p%n)*(p%n)%n; k>>=1; } return ans=(ans+x)%n; } int main(){ int n=in,m=in,k=in,x=in; printf("%d",calc(n,m,k,x)); return 0; }