最大公约数：辗转相除法， 0和a的最大公因子为a;
int gcd(int a, int b){ if(b==0) return a; return gcd(b, a%b); }
int gcd(int a, int b){ return !b ? a : gcd(b, a%b); }
a和b的最小公倍数： 设a,b的最大公因子为d, 则最小公倍数为ab/d， 但是ab可能会导致溢出，应该先算除法再算乘法，即最小公倍数为a/d*b
1 int gcd(int a, int b){ 2 return !b ? a : gcd(b, a%b); 3 } 4 5 int lcm(int a, int b){ 6 return a/gcd(a, b)*b; 7 }
分数运算：
用结构体保存分子，分母；为了避免乘法溢出， 分子分母用long long 保存， 满足以下条件
1.让分母非负数
2.如果分母为0， 规定分子为1
3.分子，分母互质
分数的化简：
1.如果分母为负， 分母取绝对值， 分子取相反值
2.求出分子分母绝对值的gcd,然后约分
分数除法：用除法前，先判断除数的分母是否为0， 如果是就不要调用除法函数啦
分数的输出：一般有这样的要求：
1.如果分子大于分母 以带分数的形式输出
2.如果分子除以分母为整数，就不输出分母；
3.真分数输出最简形式
1 struct Fraction{long long up, down;}; 2 3 Fraction reduction(Fraction result){ 4 if(result.down<0){ 5 result.down = -result.down; 6 result.up = -result.up; 7 }else if(result.up==0) result.down=1; 8 else{ 9 int d=gcd(abs(result.up), abs(result.down)); 10 result.up /= d; 11 result.down /= d; 12 } 13 return result; 14 } 15 16 Fraction add(Fraction a, Fraction b){ 17 Fraction result; 18 result.up = a.up*b.down + b.up*a.down; 19 result.down = a.down*b.down; 20 return reduction(result); 21 } 22 23 Fraction minu(Fraction a, Fraction b){ 24 Fraction result; 25 result.up = a.up*b.down - b.up*a.down; 26 result.down = a.down*b.down; 27 return reduction(result); 28 } 29 30 Fraction multi(Fraction a, Fraction b){ 31 Fraction result; 32 result.up = a.up*b.up; 33 result.down = a.down*b.down; 34 return reduction(result); 35 } 36 37 Fraction divid(Fraction a, Fraction b){ 38 Fraction result; 39 result.up = a.up*b.down; 40 result.down = a.down*b.up; 41 return reduction(result); 42 } 43 44 void output(Fraction a){ 45 a = reduction(a); 46 if(a.down==1) printf("%d ", a); 47 else if(abs(a.up)>abs(a.down)) printf("%d %d/%d ", a.up/a.down, a.up%a.down, a.down); 48 else printf("%d/%d ", a.up, a.down); 49 }
素数判断：循环次数最好不要用i*i<=n 来进行， 因为当i比较大的时候，可能溢出； 复杂度为O(N^1.5)) ； 在10^5范围内这个复杂度是可以接受的
1 bool isPrime(int n){ 2 if(n<2) return false; 3 int cnt = (int) sqrt(1.0*n); 4 for(int i=2; i<=cnt; i++) 5 if(n%i==0) return false; 6 return true; 7 }
高效的求解素数的方法：筛选法 复杂度为nloglogn
能求出1~maxn之间的素数个数， 素数，以及是否是素数；
1 const int maxn = 101; 2 int prime[maxn], vis[maxn]={0}; 3 int getPrime(){ 4 int pNum=0; 5 for(int i=2; i<maxn; i++){ 6 if(!vis[i]){ 7 prime[pNum++]=i; 9
for(int j=i+i; j<maxn; j += i) vis[j] = 1; 11 } 12 } 13 return pNum; 14 }
还有一种比较简单的素数表的建立方法
1 const maxn=50000; 2 vector<int> prime(maxn, 1); 3 for(int i=2; i<maxn; i++){ 4 for(int j=2; j*i<maxn; j++) 5 prime[i*j]=0; 6 }
2*3*5*7*11*13*17*19*23*19的结果已经超出int的范围，所以要求解某个数字的素数因子的时候，只需要一个大小为10的数组来保存就行了；
例题：https://www.cnblogs.com/mr-stn/p/9225971.html
求n!中有多少个素数因子；
1 int cal(int n, int p){ 2 if(n<p) return 0; 3 return n/p + cal(n/p, p); 4 }
这个方法可以方便的求解n!的结尾有多少个0，n!末尾0的个数就是因子10的个数，等于因子5的个数(因为n!中2出现的频率远高于5)，所以n!末尾0的个数等于cal(n, 5)
排列组合的计算：
1 long long res[67][67]={0}; 2 long long C(long long n, long long m){ 3 if(m==0 || n==m) return q; 4 if(res[n][m]) return res[n][m]; 5 return res[n][m] = c(n-1, m) + c(n-1, m-1); 6 }
1 const int n=60; 2 long long res[n][n]={0}; 3 void calC(){ 4 for(int i=0; i<=n; i++){ 5 res[i][0]=res[i][i]=1; 6 } 7 for(int i=2; i<=n; i++){ 8 for(int j=0; j<=i/2; j++){ 9 res[i][j] = res[i-1][j]+res[i-1][j-1]; 10 res[i][i-j]=res[i][j]; 11 } 12 } 13 }
更为简洁但是计算范围小一点的方法：在n=67, m=31的时候溢出；上面一种方法在n=67, m=33开始溢出
1 long long calC(int n, int m){ 2 long long ans=1; 3 for(long long i=1; i<=m; i++) 4 ans = ans*(n-m+i)/i; 5 return ans; 6 }
一般处理阶乘问题都是进行取模