题意就是给出个数n，求Σgcd(i,n)(1<=i<=n)。感觉好奇葩的题目，数论的题确实比较难想，没看出跟欧拉函数有什么关系。很纠结，没心情没时间继续想了。看了discussion，然后又去搜了下答案，发现有个哥们也得非常不错，就看了下思路了。
这个题的解法是枚举i(1<=i<=n)，如果i|n，那么答案加上euler(n/i) i。其实ans = Σi euler(n/i)(i<=i<=n而且i|n)。意思是从1到n的所有数字i，如果i是n的因子，那么计算 i euler(n/i)，加入答案中，euler是欧拉函数的意思。
为什么是这样的了。比如，1到n中有m个数字和n拥有公共的最大因子i，那么就需要把m i加入答案中。问题是如何计算m的个数。因为gcd(m,n) = i，可以得到gcd(m/i,n/i)=1，那么m/i就是n/i的乘法群中的数字了，那么一共存在euler(n/i)个m/i了，那么就可以推出m的个数就是euler(n/i)。
代码如下:
1 | #include <stdio.h> |
这个题是求原根的个数。所谓原根，意思是给定一个数n，存在数g，g^j能够产生乘法群Zn中所有的数字。即g^j = {x|x与n互质,1<=x<n}。如果n是奇素数p(大于2的素数)，那么满足g^j={1,2,…,p-1}。
这个题目要求求原根的个数。由费马定理由,对任意1<=x<p，即Zp中的数字，都由x^(p-1) = 1 % p。从费马定理可以看出，再往下计算就开始循环了。那么有,x^i%p(1<=i<p) = {1, 2, 3,…,p-1},意思是能够生成Zp中的所有数字。
根据上面的那个式子可以得到，x^i%(p-1)(1<=i<p) = {0, 1, 2,…,p-2}。 如果由gcd(x,p-1) = 1,那么必然存在某个x^i，使得x^ix = (p-1)%p。
因此可以得到，原根的个数是p-1的乘法群中元素的个数，也就是欧拉函数(p-1)。
代码如下：
1 | #include <stdio.h> |
这是个求离散对数的问题。以前学密码学基础的时候也接触过，但是没想到acm里面还会有这样的习题。问题的意思是给定素数P，给出方程a^x = b % p，注意有模的方程等式2边都是取模数的意思。解这样的方程有一个固定的算法，叫做baby-step算法。但是，注意限定条件是p必须是素数。
下面的图描述了这个算法：
意思很清楚，就是假设x = i m + j，那么方程可以转化为b(a^-m)^i = a^j % p。先计算出右边的值，存储在一张表里面，然后从小到大枚举左边的i（0<=i<m)，率先满足等式的就是最小的解x。
poj上面这个题用map存储(a^j,j)对的时候会超时，改成hash表存储才能过，额，毕竟理论复杂度不是一个数量级的。我的hash表是开了2个数组，一个键，一个值，用来相互验证，槽冲突的话，一直往后找位置。感觉这样的做法没有链式hash复杂度平均的样子。
代码如下：
1 | #include <stdio.h> |
这是今天想通的一个数论题，还是挺有意思的，想出来的那一瞬间yeah了一下，可是我悲剧的粗心习惯，还是交了3次才过，nm数中间空格都错了，又忘记打空行，明明字符串从25列开始，中间是4个空格的，我nc的打了5个空格，就pe了，还有不仔细看输出要求，没有输出空行，最近真没状态啊。
其实，这个题想通了就很简单了，还是数论里面的群的概念，就是加法群的生成群啊，打着随机数的幌子而已。由于又没有限定种子，限定对答案也没有影响，假设种子是0，那么数列可以表示为a step，数列要能够生成0 - mod-1中所有的数字，那么就有a step = b % mod(0<=b<mod)。
哈哈，上面那个式子就是a x = b % n这个线性同余方程了，只是有很多b了。要方程有解，不是需要满足条件gcd(a,n) | b么，意思b是gcd(a,n)的整数倍了。但是0 <= b < n啊，b会是1了，那么gcd(a,n)一定是1了哦。那么直接判断gcd(step,mod)是否为1就行了，哈哈。
关于线性同余方程ax=b%n，要有解的条件gcd(a,n)|b的解释，还是参看算法导论或者其它资料吧。。。
代码就非常简单了，如下：
1 | #include <stdio.h> |
这个题目就是解线性同余方程，(a + nc) % 2的k次 = b % 2的k次。既然以前是学信安的，对数论本来就不排斥，最近还好好看了下算法导论。这个方程转换为nc = (b-a) % 2的k次。根据数论的知识， ax = b%n，需要保证gcd(a,n)|b，意思b是gcd(a,n)的倍数，这个一下子也很难解释清楚啊，不满足这个条件，就是没解了。还有，如果有解的话，解的个数就是d = gcd(a,n)。而且其中一个解是x0 = x’(b/ d)，其中x’是用扩展欧几里德算法求出来的，满足关系式ax’+ny’=d。
但是这个题不仅仅用到数论的这些知识，因为必须求满足条件的最小解，而如果有解的话是d个，而且满足解x = x0 + i(b/d)，（1<=i<=d)。既然要求最小的解，那么对解mod(n/d)即可了，因为它们之间的差都是n/d的倍数。
代码如下：
1 | #include <stdio.h> |
这个题目是求N！后面有多少个0，注意N可能最大到10的9次。哈哈，直接枚举1-N有多少个2和5的因子，然后取小的值肯定会超时的。但是，我还是试了下，果断超时了。
那就只有想数学结论了，果断想到1-N中能被2整除的数字有N / 2。哈哈，再往后思考下，发现1-N中能被4整除的数字有N / 4个，再往后就是N / 8，一直到N 除以2的某个次方为0为止，那么把所有的值加起来就是2的因子的个数了。求5的因子的个数也是这样的方法了。
很明显，5的因子的个数一定会小于等于2的因子的个数。那么直接求5的因子的个数就行了。由于，N / 5的时候用到了向下取整，所以不能用等比数列求和公式，怎么把答案弄成一个公式，还不知道了。
PS：其实我这种思路的灵感来自于筛选素数的方法了。
代码如下：
1 | #include <stdio.h> |
这个题一看就知道是求欧拉函数。欧拉函数描述的正式题意。欧拉函数的理解可以按照算法导论上面的说法，对0-N-1进行筛选素数。那么公式n∏(1-1/p)，其中p是n的素数因子，就可以得到直观的理解了。但是计算的时候，会将这个式子变形下，得到另外一个形式。
如图所示：
但是这个题，需要考虑下，有可能n是个大素数，直接进行因子分解的话会超时的。怎么办了，只能在分解的时候判断n是不是已经成为素数了，如果是素数，答案再乘以n-1就行了。为了加快判断，我用5mb的空间搞了个素数表，大于5000000的数字只能循环判断了。
代码如下，注意求欧拉函数的代码部分：
1 | #include <stdio.h> |
通过这道题确实体会到A掉数学题确实还是需要经验了，不能猜对哪个地方会丧失精度的话，会一直wa的。其实，这道题我只想出了一半。
题意是 a的p次方 = n，其中n是32位整数，a和p都是整数，求满足条件的最大p。好吧，虽然我是在学数论，但是看到这题，我还是想起了取对数。那么可以得到，p = ln(n) / ln(a)。既然要求最大的p，那么a最小即可了。那么直接从2开始枚举a不就可以了么。
可是直接枚举a的话肯定会超时的，因为a的范围太大了，比如n的是个大素数，a的范围就是2-n了，一定超时了。然后，我又想出另外一种方法，对n分解因子，p就是所有因子的指数的最大公约数。呵呵，第二种方法更加会无情的超时，由于int范围很大，实现搞个素数表也不可能。还是感觉时间不多了，就不多想了，然后搜了下，发现一句话，意识是枚举p。顿时觉得开朗起来，因为p最多是32。由前面可以得到ln(a) = ln(n) / p。那么只要从32到1枚举p，保证a是整数即可。
后面发现这样精度难于控制，各种原因反正过不了题，看网上的代码，改成计算指数的形式了。因为 a = n的(1/p)次，这个可以用pow函数算出来，如果a是整数，那么再计算pow(a,p)就会是n了。最难控制的是精度了，还有说n是负数的情况。不知道为什么直接处理负数答案一直不对，只好把负数变为正数，同时判断p不能是偶数。
代码如下：
1 | #include <stdio.h> |
这个题是对可排序数据的实时增加删除查找，那天做比赛的时候一点都不会，想来想去觉得平衡树可以做，但是写平衡树是件很难的事情。
后面知道线段数可以做，虽然数据的范围很大，但是可以在全部读入数据后排序再离散化，然后进行线段树的操作，具体的代码没有写。
今天队友在网上发现一种用map和set可以水掉这题的方法。原来，这个方法最主要的使用了map和set里面的upper_bound操作，以前居然忘记了这个东西了。既然这样，map和set也可以查前驱和后继了，但是注意low_bound查到的是小于等于的键。这个代码，注意是用了一个map< int, set > 集合把坐标都存起来了，进行添加删除和查找后继的操作。由于查找需要查找的元素是既比x大又比y大的元素，就比较麻烦，需要循环x往后查找，但是这样就无情的超时了。然后，有一个优化，记录y的数目，那么当出现很大的y的时候，就不需要查找了，然后才过了这个题。但是，数据变成很大的y对应的x很小的话，那么绝对过不了这个题了，只能用线段树做了。
现在觉得用map和set查找前驱和后继确实能水掉一些题啊。
代码如下：
1 | #include <map> |
第一个题用到了同余的性质，这是数论里面最基本的性质，但是做题时候不一定能够自己发现。题意是n m = 11111…，给出n，用一个m乘以n得到的答案全是1组成的数字，问1最小的个数是多少。可以转换为n m = (k 10+1)，那么可以得到(k 10+1)%n==0。
当然最开始的k是1，那么我们不断的增长k = （10 * k + 1）。看增长多少次，就是有多少个1了。因为要避免溢出，所以需要不断%n。因为同余的性质，所以可以保证%n之后答案不变。
第二个用到素数筛选法。素数筛选法的原理是筛去素数的倍数，由于是从小循环到大的，所以当前的值没被筛掉的话，则一定是素数，这个判断导致复杂度不是n的平方。
poj 2551 代码：
1 | #include <stdio.h> |
1 | #include <stdio.h> |