先写一点关于最大公约数和最小公倍数的相关代码 最方便的方法（省事）就是调用algorithm库中的函数__gcd(n,m)，直接调用即可。 欧几里得算法辗转相除法
long long gcd(long long a,long long b) { if(b==0) return a; return gcd(b,a%b); }最小公倍数
long long lcm(long long a,long long b) { return a*(b/gcd(a,b)); }同余定理 如果a和b除以c的余数相同，即为a和b关于模c同余，记作a≡b(mod c)。 性质：
1.如果a≡b(mod m),x≡y(mod m)，则有a+x≡b+y(mod m)。 2.如果a≡b(mod m),x≡y(mod m)，则有ax≡by(mod m)。 3.如果ac≡bc(mod m),且c和m互质，则有a≡b(mod m)(就是说同余式两边可以同时除以一个和模数互质的数)。 4.若ac≡bd,c≡d(mod m)，且(c,m)=1(c和m的最大公约数是1),得到a≡b(mod m)。 此外，同余关系具有传递性： a和b同余，b和c也同余，可以推出a和c也是同余的 做题过程中，经常用到取模，这就是用到了同余定理。
int ex_gcd(int a,int b) { if(b==0) {x=1;y=0;return a;} int gcd=ex_gcd(b,a%b); int tmp=x;x=y; y=tmp-a/b*y;//扩展欧几里得算法 return gcd; } //最后得到的x即为原同余方程的一个可行解;排列组合 公式 从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，记作 A(n,m） A（n,m） = n!/(n-m)! 关于排列数，在网上看到了一个看起来就很厉害的算法（p为取模）
long long mult(long long x, long long y, long long P){ x %= P; y %= P; long long k = x*y; long long j = (long long)(((long double)x*y+0.5)/P); long long ans = ( (k - j * P) %P + P) % P; return ans; }其次还有类似快速幂的快速乘
long long mult(long long i, long long j, long long p){ L ans=0; while(j){ if(j & 1) ans = (ans+i) % p; i = (i+i) % p; j >>= 1; } return ans; }递归方法
long long mult(long long i, long long j, long long p){ if(j <= 1) return i*j; long long t = mult(i, j>>1, p); t += t; if(j & 1) t += i; return t % p; }从n个不同元素中取出m(m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。记作 C(n,m) C（n,m） = n!/(m!*(n-m)!) (n>=m)
long long factorial(long long number) { if(number<=1) return 1; else return number*factorial(number-1); } int combinator(int n,int m) { int temp; if(n<m) { temp=n; n=m; m=temp;} return factorial(n)/(factorial(m)*factorial(n-m)); } result=combinator(a,b);