欧拉函数一般形式:
当 n 为素数时: phi(n) = n-1
当 n 为合数时: phi(n) = n∏(1-1/p) 其中(p为n的素数因子)

题目pku1091，要求我们求 x1..xn,m这样的序列的个数，其中xi(1<=i<=n), 使 gcd(x1, ..,xn,m)=1;
我们按欧拉函数的形式猜想如下方程：
当 n 为素数时: phi(m,n) = m^n-1
当 n 为合数时: phi(m,n) = m^n∏(1-1/p^n) 其中(p为n的素数因子)

不给出严格数学证明(不会-_-)，上两式具体含义：
当 n为素数 phi(m,n) = m^n-1 显然成立
当 n 为合数时 可以假象有一个m进制n位的数，然后其中一位有m的约数p的概率为1/p, 则n位同时有p的约数的概率就为(1-1/p^n), 运用乘法原理，可以得式 phi(m,n) = m^n∏(1-1/p^n)
 
code:

(1)定理:设x0,x1,x2,...是无穷实数列,xj>0,j>=1,那么,
      (i)对任意的整数 n>= 1, r>=1有
            <X0,...,Xn-1,Xn,...,Xn+r> = <X0,...,Xn-1,<Xn,...,Xn+r>> 
            =   <X0,...,Xn-1,Xn+1/<Xn+1,...,Xn+r>>.
      特别地有
            <X0,...,Xn-1,Xn,Xn+1> = <X0,...,Xn-1,Xn+1/Xn+1>
      注:用该定理可以求连分数的值

(2)对于连分数数数列 <X0,...Xn> 有递推关系:
      Pn = XnPn-1+Pn-2;
      Qn = XnQn-1+Qn-2;
      定义:  P-2 = 0; P-1 = 1; Q-2 = 1; Q-1 = 0;
      所以:  P0 = X0; Q0 = 1; P1 = X1X0+1; Q1 = X1;
      特别地:当 Xi=1 时, {Pn}, {Qn}为Fbi数列

(3)pell方程: x^2+ny^2=+-1的解法:
      若n是平方数,则无解, 否则:
      先求出sqrt(n)的连分数序列<x0,x1..xn> 其中xn = 2*x0;
      对于 x^2+ny^2=-1
      若n为奇数,则 x=Pn-1, y=Qn-1; n为偶数时无解
      对于 x^2+ny^2=1
      若n为偶数,则 x=Pn-1, y=Qn-1; n为奇数时x=P2n-1, y=Q2n-1
      注:以上说的解均为最小正解
      
      
      
      

问题简单来说就是 a = ai (mod ni)   求未知数a,
 以下小结略去证明, 只是对定理作了必要的解释, 要了解相关定理,可查阅数论资料.

中国余数定理:
      设 n=n1*n2...nk, 其中因子两两互质.有:  a-----(a1,a2,...,ak), 其中ai = a mod ni, 则 a和(a1,a2,...,ak)关系是一一对应的.就是说可以由 a求出(a1,a2,...,ak), 也可以由(a1,a2,...,ak)求出a

推论1:
      对于 a=ai  (mod ni) 的同余方程,有唯一解

下面说说由(a1, a2, ..., ak)求a的方法:
定义 mi = n1*n2*...nk / ni;   ci = mi(mf  mod ni);   其中 mi*mf  mod ni = 1;
         则 a = (a1*c1+a2*c2+...+ak*ck)      (mod n)      (注:由此等式可求a%n, 当n很大时)

中国剩余定理关键是mf的求法,如果理解了扩展欧几里得 ax+by=d, 就可以想到:
                     mi*mf  mod ni = 1 => mi*mf+ni*y=1;

代码如下:

 

 

对于扩展欧几里得主要部分说明:
1. d' = bx'+(a mod b)y', d' = gcd(b, a mod b);
    设 d = gcd(a, b), 因为 d = d', 所以
    d = d' = bx'+(a mod b)y' = bx' + (a-floor(a/b)*b)y' = ay'+b(x'-floor(a/b)y');
    故有迭代:
    x = y'; y = x'-floor(a/b)y';

对于解方程主要部分说明:
1.首先给出两个定理(证明请查看相关数论书):
   A. 方程 ax = b (mod n) 有解, 当且仅当 gcd(a, n) | b;
   B. 方程 ax = b (mod n) 有d个不同的解, 其中 d = gcd(a, n);
2.证明方程有一解是: x0 = x'(b/d) mod n;
   由 a*x0 = a*x'(b/d) (mod n)
         a*x0 = d (b/d) (mod n)   (由于 ax' = d (mod n))
                 = b (mod n)
   证明方程有d个解: xi = x0 + i*(n/d)  (mod n);
   由 a*xi (mod n) = a * (x0 + i*(n/d)) (mod n)
                             = (a*x0+a*i*(n/d)) (mod n)
                             = a * x0 (mod n)             (由于 d | a)
                             = b

代码如下:

    好久没写了，主要是不知道写什么，发个刚写好的比较通用的堆吧，sigh~

    http://www.cppblog.com/qywyh/articles/28653.html