Happy 2012/2004 作者: rin 时间: October 24, 2015 分类: Algo [http://acm.bjfu.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1087](http://acm.bjfu.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1087 "http://acm.bjfu.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1087") ###描述 Consider a positive integer X,and let S be the sum of all positive integer divisors of 2012^X. Your job is to determine S modulo 29 (the rest of the division of S by 29). Take X = 1 for an example. The positive integer divisors of 2012^1 are 1, 2, 4, 503, 1006 and 2012. Therefore S = 3528 and S modulo 29 is equal to 19. ###输入 The input consists of several test cases. Each test case contains a line with the integer X (1 <= X <= 1000000). A test case of X = 0 indicates the end of input, and should not be processed. ###输出 For each test case, in a separate line, please output the result of S modulo 29. ###样例输入 ``` 1 100000 ``` ###样例输出 ``` 19 2 ``` 题目大意是 给定一个$$X$$，求$$2012^{X}$$所有因数的和，结果模上29 记 $$S(n)$$ 为 $$n$$ 的所有因数之和，有： ```math \begin{array}{l} S(2)=1+2=3 \\ S(3)=1+3=4 \\ S(4)=1+2+4=7 \\ S(5)=1+5=6 \\ S(6)=1+2+3+6=12 \\ S(7)=1+7=8 \\ S(8)=1+2+4+8=15 \\ S(9)=1+3+9=13 \\ S(10)=1+2+5+10=18 \\ \qquad ... \\ S(14)=1+2+7+14=24 \\ S(15)=1+3+5+15=24 \\ S(16)=1+2+8+16=27 \\ \qquad \cdots \\ S(24)=1+2+3+4+6+8+12+24=60 \\ \qquad \cdots \\ S(30)=1+2+3+5++6+10+15+30=72 \\ \qquad \cdots \\ \end{array} ``` 由<ruby> 观察 <rt> naodong </rt></ruby>有： ```math \begin{array}{l} \qquad \cdots \\ S(6)=S(2)\times S(3)=12 \\ S(10)=S(2)\times S(5)=18 \\ S(14)=S(2)\times S(7)=24\\ S(15)=S(3)\times S(5)=24\\ S(24)=S(3)\times S(8)=60 \end{array} ``` <!--more--> 对于分解成多个数相乘的情况也成立： ```math S(30)=S(2)\times S(3)\times S(5)=72 ``` 但： ```math \begin{array}{l} S(16)\neq S(2)\times S(8) \\ S(24)\neq S(2)\times S(12) \\ S(24)\neq S(4)*S(6) \end{array} ``` 则可以说当$$a, b, c, \cdots$$中任意两个的$$gcd = 1$$ 时 $$S(n)=S(a)\times S(b)\times S(c)\times S(\cdots \cdots)$$ 其中 $$n=a\times b\times c\times \cdots$$。函数$$S$$即积性函数。 反过来看就是: ```math \begin{array}{l} S(2)\times S(7)=S(14) \\ \Rightarrow (1+2)\times (1+7) \\ =(1+7+2+14)=S(14) \end{array} ``` ```math \begin{array}{l} S(3)\times S(8)=S(24) \\ \Rightarrow (1+3)\times (1+2+4+8) \\ =(1+3)*(1+2)+(1+3)*(4+8) \\ =(1+2+3+6+4+8+12+24)=S(24) \end{array} ``` ```math \begin{array}{l} S(2)\times S(8) \neq S(16) \\ \Rightarrow (1+2)\times (1+2+4+8) \\ =(1+2\color{red}{+2}+4\color{red}{+4}+8\color{red}{+8}+16) \neq S(16) \end{array} ``` ```math \begin{array}{l} S(4)\times S(6) \neq S(24) \\ \Rightarrow (1+2+4)\times (1+2+3+6) \\ =(1+2\color{red}{+2}+3+4\color{red}{+4}+6\color{red}{+6}+8+12\color{red}{+12}+24) \end{array} ``` 最后两式有因子重复了 因此要求 $$\gcd(a, b) = 1$$ **每个合数都可以写成几个质数（素数）相乘的形式，**为了使得对于题目给定的底数$$n$$能使用$$S(n)=S(a)\times S(b)\times \cdots$$需要将$$n$$分解成这种质因数形式（因为不同素数之间$$\gcd=1$$） 但是，如果分解出了$$a$$个相同的质因数$$x$$，$$\gcd(x, x)=x$$，则不一定能保证$$\gcd=1$$ 把这几个质因数单独拿出来，写成$$x^{a}$$ 对于数$$x^{a}$$来说，它的因数显然只有$$x^{0}, x^{1},x^{2} \cdots, x^{a}$$，这些数的和就是一个 公比为$$x$$首项为$$1$$的等比数列前$$a+1$$项和（这个$$a+1$$是因为我们从0开始数）。 此时将题目中给的数分解： ```math \begin{array}{l} 2012=2^{2}\times 503 \\ \Rightarrow S(2012)=(sum\space of\space sequence)+S(503) \\ =(1+2+4)+(1+503) \end{array} ``` 那 这只是题目里$$X=1$$时的情况，其他情况呢？先套上$$X$$ ```math \begin{array}{l} 2012^{X}=2^{2X}*503^{X} \\ \Rightarrow 2012^{X} \\ =2\times 2\times 2\times \cdots \\ \times ( rest\space 2s)\times 2\times 2 \times 503\times 503\times 503\times \cdots \\ \times (rest 503s)\times 503\times 503 \end{array} ``` 现在情况和前一段相似，$$S(2012)=$$首项为1公比为2的数列的前$$2X+1$$项和 $$\times$$ 首项为1公比为503的数列的前$$X+1$$项和 使用等比数列的公式 ```math S_{n}=\frac{a_{1}(1-q^{n})}{1-q} (q \neq 1) ``` 代入$$a_{1}=1, q=2, n=2X+1$$和$$a_{1}=1, q=305, n=X+1$$有 ```math S(2012^{X}) = \frac{503^{X+1}-1}{502}\times (2^{2X+1}-1) ``` 还没完，题目要求结果要模上29，于是 ```math S(2012^{X})\% 29 = \left [ \frac{503^{X+1}-1}{502}*(2^{2X+1}-1)\right ] \% 29 ``` 左边那串好难算啊。先消掉除法， ```math \begin{array}{l} \left [ \frac{503^{X+1}-1}{502}*(2^{2X+1}-1)\right ] \% 29 \Rightarrow \\ \left [ (503^{X+1}-1)*(2^{2X+1}-1)*13 \right ] \% 29 \Rightarrow \end{array} ``` 然后把里面底数也变小点 ```math \begin{array}{l} \left [ (503^{X+1}-1) \% 29 * (2^{2X+1}-1) \% 29 * 13 \% 29 \right ] \% 29 \Rightarrow \\ \left [ ((503 \% 29)^{X+1}-1) * ((2 \% 29)^{2X+1}-1) * 13 \right ] \% 29 \Rightarrow \\ \left [ (10^{X+1} \% 29 -1) * (2^{2X+1} - 1) * 13 \right ] \% 29\Rightarrow \end{array} ``` 蓝后就可以使用快速幂取模之类的东西$$qp(a,b,p) = a^{b}\% p $$ ```math ans =\left [(qp(10,x+1,29)-1) * (qp(2,2*x+1,29)-1) * 13 \right ] \% 29 ``` 完工 ```cpp int main(){ int x; while(EOF!=scanf("%d", &x) && x) { int ans = (qp(2,2*x+1,29)-1)%29 * (qp(10,x+1,29)-1)%29 * 13; ans = ans % 29; printf("%d\n", ans); } return 0; } ``` 当然结果是循环的 可以再粗暴一些 ```cpp int main(){ int x; int a[28] = {1,19,19,12,14,1,7,21,12,1,5,19,2,13,2,2,16,21,11,21,3,28,19,16,14,8,28,0}; while(EOF!=scanf("%d", &x) && x) printf("%d\n", a[x%28]); return 0; } ``` 标签: 数论