去年合肥網絡賽的題目，今天終于給搞定了。確切的說不是完全獨立想出來的，看了網上的一點提示（用歐拉定理），然后想了好幾次終于想出來了。
　　題目大意是給定一個L（L不大于2000000000），求最小長度的能整除L的都是8的數，輸出長度，如果沒有輸出0。設長度為n的話，那么這個全為8的數可以表示成8 + 80 + 800 + ...是一個等比數列，變換后得到8 * (10 ^ n - 1) / 9 = k * L。如果L中2的因子數不大于3個，那么可以除掉。之后等式可以寫成10 ^ n - 1 = 9 * k * L，也就可以轉換成一個模方程：10 ^ n = 1 mod 9L。根據歐拉定理，一定要10和9 * L互素才能有解，這樣就可以判定出無解的情況了。之后相當于求一個原根，求出9L的歐拉函數，設其為phi，那么n一定是phi的約數才可以滿足條件，枚舉phi的約數就可以了。
　　這個題目變態的一個地方在于9L和phi都可能很大，int表示不下，要用long long，這么大的模簡單的乘法會溢出，也要寫成二分的形式。中間有好幾個地方我都用了int，結果導致溢出，超時了2次。總的來說這是個很好的數論題目，以后這種題目應該多練習一些。

　　是個經典問題了，求滿足a ^ 2 + b ^ 2 = c ^ 2且a、b、c兩兩互質的三元組個數，其中a、b、c都小于等于n，同時還要求出n以內不屬于三元組（不必互質）的數的個數，其中n <= 1000000。
　　數據范圍很大，單純的n ^ 2的枚舉肯定是不行的。我發現互質的三元組不多，想找一個辦法求出互質的，然后篩出其他的三元組（乘以倍數），但是仍然想不出怎樣很快找到互質的三元組。到網上查了一下，找到了一個很好的網站（http://xserve.math.nctu.edu.tw/people/cpai/carnival/fraction/05.htm）講解這個問題。
　　首先只需找到互質的a和b就可以了，其余的可以通過乘以一定的倍數得到。首先a和b必須不能都是奇數，否則的話，不妨設a = 2p + 1, b = 2q + 1, c = 2r。帶入a ^ 2 + b ^ 2 = c ^ 2有：2 * (r ^ 2 - p ^ 2 - q ^ 2 - p - q) = 1，出現了矛盾。這樣必然a和b一奇一偶，設a是偶數。恒等變換一下：（這里是x ^ 2 + y ^ 2 = z ^ 2，x是偶數）

　　令u = (z - y) / 2，v = (z + y) / 2。因為y、z互質，那么u、v互質。如果不互質，有v = ku，變換后得到：z / y = (k + 1) / (k - 1)。因為z和y互質，這樣這個等式的解只能是z = k + 1且y = k - 1。這樣的話u = 1。可以理解為這也是互質的特殊情況(gcd = 1)。這樣(x / 2) ^ 2 = u * v，u和v沒有公共的質因數，因此必然u和v都是完全平方數。接下來的事情就比較簡單了，令u = m ^ 2，v = n ^ 2，然后利用m和n表示x、y、z有：y = n ^ 2 - m ^ 2，x = 2 * m * n，z = n ^ 2 + m ^ 2。這樣題目中數據范圍1000000，而枚舉m和n的范圍最大1000，這個復雜度就可以接受了。枚舉的時候不用擔心出現重復的互質的x與y，因為這里x一定是偶數，如果x和y已經互質，那么y一定是奇數，解是唯一的。
　　很囧的是這個巧妙的方法居然公元前250年就有大牛想到了（丟番圖），實在orz！

 

　　定義一個正整數n的函數F(n)為n的每位數的乘積。一個數是good如果F(n)不為0并且n能整除F(n)，一個數是完美數當且僅當n是good并且n+1也是good。現在問一個長度是k位的數中有多少個完美數，其中k不大于1000000。
　　不得不承認這是一個非常經典的鍛煉分析問題能力的題目。設n = a1a2...an，因為F(n)不為0，所以n + 1 = a1a2...(an+1)。根據題目意思，我們可以列出等式：n + 1 = q * (a1 * a2 * ... * (an + 1))，又n = p * (a1 * a2 * ... * an)。令A = a1 * a2 ... * an-1，整理前面的等式可以得到：(q * an + q - an) * A = 1。因為這里面都是整數，顯然A = 1，也就是說a1，a2，...，an-1都是1。問題一下子就變得簡化了很多，比起之前的單純枚舉可以說是進了一大步。但是如果枚舉最后一位判斷是不是可行復雜度依然很高，需要進一步討論。首先an是1、2、5對應的數都是good；an為3的時候，如果是good必須前面n-1個1加和是3的倍數；an為4的時候需要最后兩位被4整除才行，14不滿足條件；同理an為6的時候也必須前面n-1個1加和是3的倍數；an為8的時候需要后三位的數被8整除，顯然也不可能；經過一番討論，就剩7這個特別的數字了。用一堆1對7試除一下發現一個規律，111111恰好整除7，六個數一循環。這樣只需判斷(an - 1)是否整除6就可以了。
　　綜上所述，對于一個k位的數字，如果k為1，那么結果是8。如果k大于1，結果首先是1，如果k-1能被3整除，結果加2；如果k-1能被6整除，結果再加1。這樣O(1)的時間復雜度就出結果了，仔細分析問題后得出的做法真強大啊。 　　假設現在有p個球放入k個盒子中，對于球和盒子的屬性分別做限制，然后詢問方法數。這里的屬性限制分別包括：球是不是相同的，盒子是不是相同的，盒子是否為空。
　　首先看最簡單的情況：盒子可以為空，球和盒子都是不同的。那么一共有k ^ p種放法。如果規定盒子是非空的，那么就需要利用容斥原理，設第i個盒子是空的為一種屬性，那么分別計算一個盒子為空的方法數，兩個盒子為空。。。然后利用容斥原理就行了。
　　現在規定球是不同的，盒子是相同的且盒子不能為空。這是第二類stirling數，S(p, k) = k * S(p - 1, k) + S(p - 1, k - 1)。如果規定盒子可以為空，那么就是第p個Bell數，也就是對第二類stirling數k從0到k求和。
　　如果盒子相同，球也相同，這時候盒子空不空都無所謂了，就是一個整數劃分問題，非空的話先給每個盒子裝一個球再算就行了。
　　最后一種情況是盒子不同，球相同，如果盒子可以為空，那么問題就變成了經典的x1 + x2 + ... + xk = p，x取值范圍0到p的解的個數。這是經典的組合數學問題，利用隔板法求得答案是C(k + p - 1, p)。如果盒子非空，那么就是把x的取值范圍變成1到p就行了，答案是C(p - 1, p - k)。
　　lord wu給去年省賽出的一個題目，今天終于給搞出來了。
　　一開始完全想錯了方向，總是覺得很復雜。后來發現計算SG值的時候，對于限制的狀態只能走到0，也就是必勝態，這樣就是一個裸的SG分解的題目了。接下來就很簡單了，利用容斥原理算出SG值，結論同Nim。
　　感覺博弈的題目做起來還是很困難的，一方面SG值的計算不容易，很多時候只能通過規約成一個經典模型來計算；另一方面博弈的題目變化多端，很難有什么規律可言。不過SG分解還是王道，用這個武器解決簡單的博弈問題還是綽綽有余的。
附2645代碼：