hdu1452 Happy 2004

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

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

奇性函數：

在數論中，積性函數<喎?http://www.Bkjia.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="http://www.2cto.com/uploadfile/Collfiles/20140409/20140409090159258.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;
    }