hdu1452 Happy 2004

原题：http://acm.hdu.edu.cn/showproblem.php pid=1452

等比数列求和公式：（之前忘记了。+ =）

奇性函数：

在数论中，积性函数< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPsrH1rjSu7j2tqjS5dPyzqrV/dX7yv08ZW0+bjwvZW0+ILXEy+PK9bqvyv08ZW0+ZihuKTwvZW0+o6zT0Mjnz8LQ1NbKo7o8ZW0+ZigxKQogPSAxPC9lbT6jrMfStbE8ZW0+YTwvZW0+ILrNPGVtPmI8L2VtPiC7pdbKyrGjrDxlbT5mKGFiKSA9IGYoYSkgZihiKTwvZW0+oaM8L3A+CjxwPgrI9NK7uPa6r8r9PGVtPmYobik8L2VtPiDT0Mjnz8LQ1NbKo7o8ZW0+ZigxKSA9IDE8L2VtPqOsx9K21MG9uPbL5tLi1f3V+8r9PGVtPmE8L2VtPiC6zTxlbT5iPC9lbT4gtvjR1KOssrvWu8/e1eLBvcr9u6XWysqxo6w8ZW0+ZihhYikgPSBmKGEpZihiKTwvZW0+ILa8s8nBoqOs1PKzxrTLuq/K/c6qzerIq7v90NS6r8r9oaM8L3A+CjxwPgrU2sr9wtvS1M3itcTG5Mv7yv3Rp8Hs0/LW0Mv5zLi1vbXEPHN0cm9uZz67/dDUuq/K/Twvc3Ryb25nPs2os6PKx9a4PHN0cm9uZz7N6siru/3Q1Lqvyv08L3N0cm9uZz6hozwvcD4KPHA+CjwvcD4KPGgyPgrA/dfTPC9oMj4KPHVsPgo8bGk+ptUoPGVtPm48L2VtPikgo63Ft8CtptW6r8r9o6y8xsvj0+s8ZW0+bjwvZW0+u6XWyrXE1f3V+8r91q7K/cS/PGxpPqbMKDxlbT5uPC9lbT4pIKOtxKyxyM7ay7m6r8r9o6y52NPat8fGvbe9yv21xNbK0vLX08r9xL88bGk+Z2NkKDxlbT5uPC9lbT4sPGVtPms8L2VtPikgo63X7rTzuavS8tfTo6y1sTxlbT5rPC9lbT65zLaotcTH6b/2PGxpPjxpbWcgY2xhc3M9"tex" alt="\sigma_k" src="https://www.cppentry.com/upload_files/article/49/1_olr8y__.png">(n): 除数函数，n的所有正因子的k次幂之和，当中k可为任何复数。在特例中有：

• (n) = d(n) - n的正因子数目
• (n) = (n) - n的所有正因子之和
• 1(n) －不变的函数，定义为 1(n)=1 （完全积性）
• Id(n) －单位函数，定义为 Id(n)=n （完全积性）
• Id_k(n) －幂函数，对于任何复数、实数k，定义为Id_k(n) = n^k （完全积性）
  • Id₀(n) = 1(n) 及
  • Id₁(n) = Id(n)
  • ε(n) －定义为：若n = 1，ε(n)=1；若n > 1，ε(n)=0。有时称为“对于狄利克雷卷积的乘法单位”（完全积性）
  • (n/p) －勒让德符号，p是固定质数（完全积性）
  • λ(n) －刘维尔函数，关于能整除n的质因子的数目
  • γ(n)，定义为γ(n)=(-1)^ω(n)，在此加性函数ω(n)是不同能整除n的质数的数目
  • 所有狄利克雷特征均是完全积性的
  • 
    //上面的资料摘自维基百科。

    可见本题目为：除数函数，不完全奇性函数。

    
    

    const int INF=0x3f3f3f3f; 另外参见了大神的代码，发现最大值可以这么表示。
    

    


    原因如下：http://blog.csdn.net/dr5459/article/details/8211408

    有如下性质：

    1、当gcd(a,b)=1时，s[a*b]=s[a]*s[b].

    2、当p为素数时，s[p^n]=p^0+p^1+……+p^n=(p^(n+1)-1)/(p-1)

    3、（a * b ) / c % M = a % M * b % M * inv(c);

    其中inv(c)即满足 (c*inv(c))%M=1的最小整数,这里M=29

    inv(1）= 1， inv(2)=15,inv(166)=18;

    S((2^2)^x) * S(3^x) * S(167 ^ n) = S(2004^n);

    //============================================================================
    // Name        : Math_hdu1452.cpp
    // Author      : vit
    // Version     :
    // Copyright   : Your copyright notice
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #include 
           
            
    #include 
            
              #include 
             
               #define MOD 29 using namespace std; int pow(int a,int b) { int ans=1; while(b) { if(b&1)//judge odd or even ans = (ans * a) % MOD; a = a * a % MOD; b=b>>1; } return ans; } int main() { int x; int a, b, c; while(cin >> x && x){ a = (pow(2,2*x + 1) - 1) * 1 % MOD; b = (pow(3,x + 1) - 1) * 15 % MOD; c = (pow(167, x + 1) - 1) * 18 % MOD; cout << a * b * c % MOD << endl; } return 0; }