去年合肥网络赛的题目，今天终于给搞定了。确切的说不是完全独立想出来的，看了网上的一点提示（用欧拉定理），然后想了好几次终于想出来了。
　　题目大意是给定一个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代码：