ZOJ3707 Calculate Prime S 數論好題目啊

這道題目真的很難啊，不是那麼好做的，現場比賽若是遇到這個 真心很難去花時間研究，我做了好久 WA了 10多把終於過了

總是做算法，不如來個陶冶情操的文章一篇： http://www.sanwen.net/subject/3628849/

有一個集合{1,2,3,,,n}, Sn表示 他的特殊子集數（子集中元素不允許出現連續的現象），比如 {1,2}這個就是非法的，Sn與前面所有的Si都互素的sn叫做 PRIME S，

求不小於第K個PRIME S的 能被X整除的數 對M取模的結果

我的想法沒那麼高深，一開始就按照題目要求，列舉找出SN的值，後來多寫幾個 發現了 是 fibonacci數列，題目中把 Sn與前面所有的Si都互素的sn叫做 PRIME S，再在 fibonacci數列裡找找，發現 其實如果 F[n]是素數的話 那麼 就滿足題目要求，那麼其實F[n] 是PRIME S 當F[n] 為素數，所以 題目的大體方向救出來了，就是 fibonacci數列構造出來，但是K的最大值有10^6所以 不可能遞推出來，可以用矩陣構造

構造矩陣 A[2][2] ={1,1,1,0}，這個在學矩陣快速冪的時候遇到過，用上了

對於輸出還有一個特殊的地方 那就是 如果 X/Y%MOD,如果Y能夠整除X，這個式子可以轉化為 (X%(MOD*Y))/Y,證明

如果b與c互素，則(a/b)%c=a*b^(phi(c)-1)%c

如果b與c不互素，則(a/b)%c=(a%bc)/b

這只是我的一些過程 還有大牛的分析，可能更好：來自http://www.cnblogs.com/xinyuyuanm/archive/2013/05/29/3106627.html

fibonacci數列的性子：

1.gcd(fib(n),fib(m))=fib(gcd(n,m))

證明：可以通過反證法先證fibonacci數列的恣意相鄰兩項一定互素，然後可證n>m時gcd(fib(n),fib(m))=gcd(fib(n-m),fib(m))，遞歸可

求gcd(fib(n),fib(m))=gcd(fib(k),fib(l))，最後k=l，不然繼承遞歸。K是通過展轉相減法求出，易證k=gcd(n,m)，所以gcd(fib(n),fib(m))

=fib(gcd(n,m))。

2.如果fib(k)能被x整除，則fib(k*i)都可以被x整除。

3.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1

4.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)

5.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1

6.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)

7.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1

8.f(m+n)=f(m-1)·f(n-1)+f(m)·f(n)

9.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1)

10.f(2n-1)=[f(n)]^2-[f(n-2)]^2

11.3f(n)=f(n+2)+f(n-2)

12.f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]

還有一個結論：

盤算(a/b)%c 其中b能整除a

如果b與c互素，則(a/b)%c=a*b^(phi(c)-1)%c

如果b與c不互素，則(a/b)%c=(a%bc)/b

對於b與c互素和不互素都有(a/b)%c=(a%bc)/b成立

#include
#include
#include
#include
#include
#include
#include
#include
#include

3 3 10

101 117 100007

*/