hdu 1452 Happy 2004

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1452 問題解決の考え:私もネット上の大牛のコードに基づいて、自分でゆっくり整理しています.実はよく分かりません.2004^Xの因子とs(2004^X)mod Mを計算します.M=29 s(2004^X)%29因子とsは積性関数です.
2004^X=4^X*3^X*167^X s(2004^X)=s(2^(2 X)*s(3^X)**s(167^X)
pが素数=>s(p^X)=1+p+p+2+…+p^X=(p^(X+1)-1)/(p-1)
s(2004^X)=(2 X+1)-1)*(3^(X+1)-1)/2*(167^(X+1)-1)/166
167%29=22
s(2004^X)=(2 X+1)-1)*(3^(X+1)-1)/2*(22^(X+1)-1)/21
(a*b)/c%M=a%M*b%M*inv(c)
c*inv(c)=1%Mモードは1のすべての数inv(c)は最小でcで割り切れるものです.

inv(2)=15,  inv(21)=18    2*15=1 mod 29, 18*21=1 mod 29

s(2004^X)=(2 X+1)-1)*(3^(X+1)-1)/2*(22^(X+1)-1)/21=(2^(2 X+1)-1)*(3^(X+1)-1)15(22(X+1)-1)*18

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int quickmod(int a,int b)//   
{

    int ans=1;
    a%=29;
    while(b)
    {
        if(b&1)
        ans=(ans*a)%29 ;
        b>>=1;//b/=2;
        a=(a*a)%29;
    }
    return ans ;
}
//       。。。。
int main()
{
    int n;
    int a,b,c;
    while(scanf("%d",&n),n)
    {
         a=(quickmod(2,2*n+1)-1);
         b=(quickmod(3,n+1)-1)*15;// 15 2 mod 29 
         c=(quickmod(22,n+1)-1)*18;//18  21 mod 29 
         printf("%d
",a*b*c%29);
    }
    return 0;
}