数论公式

1.Fibonacci 前n项平方和;

a12+a22+......a[n]2=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为质数;

φ(ap) = ap – ap-1=( a – 1 )∗ap-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);
φ(NZp)=φ(NZp-1)*Z.

6.关于eula的定理

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

(2).费马小定理:因为当p为质数时,φ(p)=p-1;所以 ap-1≡ 1 (mod p);【指数的mod值】

7.乘法逆元

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

也可以用extgcd求逆元;

8.ax=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=1i   ⌊i/j⌋  :这个东西是奇性函数,然后快筛

代码自己去找
10.卢卡斯定理

Cnm(mod p ) 【p为质数】=Cn/pm/p * Cn%pm%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)级别的

发表评论

邮箱地址不会被公开。 必填项已用*标注