歐拉函數一般形式:
當 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://m.shnenglu.com/qywyh/articles/28653.html