1452 happy 2004.cpp

来自「威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。」· C++ 代码 · 共 59 行

/* 
用数学软件推出了和的公式
[ 2^(2x+1)-1 ][ 3^(x+1) -1][ 167^(x+1)-1 ]
---------------------------------------------------------
(x-1)(y-1)(z-1)

每步都求余后，注意除法后的余数 
 */
#include <stdio.h> 
#include <math.h> 

int DFS(int x,int y) 
{ 
   int temp,i;
    
    x%=29;
    temp=1;
    while(y>1)
    {
		if(y%2==1)
		{
			temp*=x;
			temp%=29;
			x*=x;
			x%=29;
			y/=2;
		}
		else
		{
			x*=x;
			x%=29;
			y/=2;
		}
	}
    return (x*temp)%29;
} 

int main()
{
    int x,temp1,temp2,temp3,sum;
    while(scanf("%d",&x) && x)
    {
        temp1=DFS(3,x+1)-3+29;
        if(temp1%2==1)
			temp1+=29;
        temp1/=2;
        temp1%=29;
        temp2=(DFS(2,2*x+1)-2+29)%29;
        temp3=DFS(167,x+1)-167%29+29;
        while(temp3%166)
			temp3 += 29;
        temp3/=166;
        temp3%=29;
        sum=temp1+temp2+temp3+temp1*temp2+temp1*temp3+temp2*temp3+temp1*temp2*temp3+1; 
        printf("%d\n",sum%29); 
    } 
    return 0; 
}