(gcd(x^a-1,x^b-1)=x^{gcd(a,b)}-1) ((x>1,a,b>0)) (HDU 2685)
(gcd(fib[m],fib[n])=fib[gcd(m,n)])
(lcm(ka,kb)=k*lcm(a,b))
(a>b,gcd(a,b)=1,则gcd(a^m-b^m,a^n-b^n)=a^{gcd(m,n)}-b^{gcd(m,n)})
(设G=gcd(C_n^1,C_n^2,...,C_n^n)则G的值为:) (HDU 2582)
- n为素数：n
- n有多个素因子：1
- n只有一个素因子：该因子
(sum_{i=1}^ngcd(i,n)=sum_{d|n}d*varphi(n/d))
(sum_{d|n}mu(d)=[n=1])
(sum_{d|n}frac{mu(d)}{d}=frac{varphi(n)}{n})
(n=sum_{d|n}varphi(d))
最小生成树中的最大边权为所有生成树中最大边权的最小值(所有生成树中最大边权的最小值在MST上)
有向无环图的生成树个数等于入度非零的节点的入度积
费马小定理：(p)为质数，整数(a)不是(p)的倍数，则(a^{p-1}equiv1(mod) (p))
威尔逊定理：(p)为质数，等价于((p-1)!equiv-1(mod) (p)) 即 (p|((p-1)!+1)，(p-2)!equiv1(mod) (p)) (HDU 6608) (此处为阶乘)
费马-欧拉定理：若(n,a)为互质正整数，则：(a^{varphi(n)}equiv1(mod) (n))
霍尔定理： 判断二分图是否完美匹配的充要条件：首先要求|X|==|Y|（左右点数相等），对于任意的X的子集(a)都有(|a|<=|b|),其中(b)是(a)能达到的点集的并
霍尔定理推论：对于二分图(G=lbrace X+Y,E
brace)，最大匹配(M=|X| - max(|S| - |N(S)|)) ((S)为(X)的子集，(N(S))为(S)所能到达的点集的并()) ((|S|)可以为0，所以后者一定不小于0()) (HDU 6667)
如果 (p\%4=3,x^2=a(mod) (p)) 那么(x=±pow(a, (p+1)/4, p))
((a+b)^pequiv a^p+b^p(mod) (p))
(n^{frac{p-1}{2}}equivpm1(mod) (p))
若(a*b-c*d=1)，则(a,b,c,d)两两互质
斐波那契求和公式：(S_n=2*a_n+a_{n-1}-1)
小于(n)且与(n)互质的数之和(S_n=n*varphi(n)/2)
对于质数(p)
- 若(n\%p=0)则(varphi(n*p)=varphi(n)*p)
- 若(n\%p!=0)则(varphi(n*p)=varphi(n)*(p-1))
- (varphi(p^k)=p^k-p^{k-1}=(p-1)*p^{k-1})
欧拉降幂 (易证后两个包括第一个,所以只需要判断(b)和(varphi(p))的大小关系来套用第二个或者第三个)
若(aequiv1(mod) (p))，则(a^{p^k}equiv1(mod) (p^{k+1}))
欧拉函数对于第(i)位的三元组((varphi(i) , varphi(i + 1) , varphi(i + 2) ))是唯一的
若(gcd(x,y,z)=G,lcm(x,y,z)=L)，则(gcd( x', y',z')=1,lcm(x',y',z')=L/G)，其中(x' = x /G，y' = y /G ，z' = z / G) (HDU4497)
(a,b)互质的充要条件是存在整数(x,y)使得(ax+by=1)
(sigma(ij)=sum_{a|i}sum_{b|j}[gcd(a,b)=1]frac{aj}{b}) ((sigma是约数和函数))
一个最简分数，如果分母中除了2和5以外，不含有其他的质因数，这个分数就能化成有限小数
(gcd(a,b) = gcd(a+b, lcm(a,b)))
(gcd(x,y,z)=gcd(x,y-x,z-y))
(n)个(m)边形最多可以把平面分成几部分，(N(1)=2)，递推公式：(N(n)=N(n-1)+2*m(n-1))，对应答案为 (m*(n*n-n)+2)
(d=gcd(n,m),则phi(m*n)=frac{d*phi(m)*phi(n)}{phi(d)})
若(n&k=k)则 (C(n,k))为奇数，否则为偶数
一个森林内部节点的度数平方和等于 2 * (长度为 2 的路径数 + 长度为 3 的路径数)
(sum_{d|n}|mu(d)|=2^{w(n)}) （(w(n)) 为(n)不同素因子个数）
积性函数的卷积仍为积性函数
(sum_{i=1}^{n}mu(i)^2=sum_{d=1}^{sqrt n}mu(d)*lfloor frac{n}{d^2}
floor)
若(b|a)，则(frac{a}{b}mod m=amod(mb)/b)
(a+b=(a igoplus b)+2*(a&b))
勾股数
(a=2n+1, b=2n^{2}+2n, c=2n^{2}+2n+1)
(a=2n+2, b=n^{2}+2n, c=n^{2}+2n+2)