数学知识积累

一、n的约数个数是O(sqrt(n))级别的。

二、n! 质因数分解的模板：
void Div(int *list,int n){
int i,j,tmp;
for (i=0;i for (i=0;i tmp=n;
while (tmp/pl[i]){
list[i]+=tmp/pl[i];
tmp/=pl[i];
}
}
}

三、勾股数定理
对于a^2+b^2=c^2
1、a=m^2-n^2
2、b=2*m*n
3、c=m^2+n^2
4、gcd(n,m)=1。
5、gcd(a,b,c)=1。
同时满足这五条式的是一组勾股数，而且对于所有满足这五条式的(m,n)乘一个k(k>=1)，即(km,kn)。就可以表示所有的勾股数，并且勾 股数和三元对(m,n,k)一一对应。
换句话说，每个勾股数都只能表示为一个三元对(m,n,k)。
并且k=1时，必须满足c%4==1才能分出来。(Fermat’s two-square theorem. A prime number with p=4n+1 can be written as the sum of two square numbers)

四、p为质数，那么(a/b) mod p=(a* b^(p-2)) mod p

五、若gcd(b,p)=1 那么 a = b*x (mod p)  只有一个0<=xφ(n)=n*（1-1/p1)(1-1/p2)….(1-1/pk),其中p1、p2…pk为n的所 有素因子。
比如：φ(12)=12*(1-1/2)(1-1/3)=4。

七、 A^x = A^(x % Phi(C) + Phi(C)) (mod C) 其中phi是欧拉函数

证明参见师父的博客http://hi.baidu.com/aekdycoin/blog/item/b6f1762565bb403fc8955908.html

 

八、在数论上的一条欧拉公式A^Phi(C)=1 (mod C)  前提是：(A,C)=1

 

九、

Fib数列的循环。

1) pi = 5, 暴力

2) 循环可能满足

  a) 是P – 1的因子

  b) 是2P + 2 的因子……

  c) 就是P……

————————————————持续更新——————————————————————————