数论公式

1.Fibonacci 前n项平方和；

a1²+a2²+......a[n]²=a[n]*a[n+1];

2.Gcd(a,b);

gcd(a,b)=gcd(b,a%b);

3.计算a*x+b*y=gcd(a,b)的一个解；

extgcd();构造x[i]=y[i-1];y[i]=x[i-1]-a/b*y[i];

4.ax+by=c的解；等价于 a*x≡c(mod p); [ax+py=c];

有解的充分必要条件是c%gcd(a,b)==0;设ax+by=gcd(a,b);的解x为k;那么，原方程的一个解就是ans=k*c/gcd(a,b);最小整数解是ans%[b/gcd(a,b)];

5.欧拉函数φ(x)

欧拉函数φ(x)定义为小于等于正整数x的数中与x互质的数的个数.

φ(1)=1;

φ(a)=a-1<=>a为质数；

φ(a^p) = a^p – a^p-1=( a – 1 )∗a^p-1 (a为质数,容斥原理);

φ(m∗n)=φ(m)∗φ(n),m与n互质.

n=∑(d|n) φ(d) (一个数约数的欧拉函数之和等于它本身)

如果光计算一个数的eula函数，可以将它质因子分解；

φ(n)=n* 连乘(a[i]-1/a[i]);(先除分母，后乘分子，a[i]为n的质因子)；
证明： 设Z为质数，N,Z互质
则有 φ(NZ)=φ(N)(Z-1)；
φ(NZ^p)=φ(NZ^p-1)*Z.

6.关于eula的定理

(1).eula定理：在a与p互质时有 a^φ(p)≡ 1 (mod p);

(2).费马小定理：因为当p为质数时，φ(p)=p-1；所以 a^p-1≡ 1 (mod p);【指数的mod值】

7.乘法逆元

a^φ(p)-1*a=1;所以a^φ(p)-1,为a的逆元；当p为质数时，a的逆元为a^p-2;

也可以用extgcd求逆元；

8.a^x=1 (mod p)

因为费马小定理,所以p-1肯定是方程的一个解，另外，最小正整数解一定是p-1的一个因子；所以暴力枚举p-1的因子即可,O(√p)；

9.求∑(i=1~n）⌊n/i⌋

(1):分块：由于n/i很多都是一样的值，所以可以把n/i都相等的分个块；nn=n/I;那么下一个块的起始元素就是i=n/nn+1;所以循环时可以跳，总时间复杂度是O(√n)的；

(2):O(n)时间，求出  (i=1~n）∑_j=1ⁱ   ⌊i/j⌋  ：这个东西是奇性函数,然后快筛

代码自己去找

10.卢卡斯定理

Cⁿ_m(mod p ) 【p为质数】=C^n/p_m/p * C^n%p_m%p(mod p)

用于处理m>=p的情况（无法求逆元）。可以递归哦!!!

11.n的约数

可以√n出解，枚举。然后记得n的约数的数量大约是√n级别的

12. n!分解质因子每个指数出现的次数

先把每个质数拿出，然后就考虑n里有多少个数因子里带了一个质数，两个质数。

所以ans[z]=n/z+n/z/z+n/z/z/z.......

13.1~x中的质数的数量

大概是x/ln(x)级别的