HDOJ 2674 N!Again(同余定理)

N!Again
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4044    Accepted Submission(s): 2177
Problem Description
WhereIsHeroFrom:             Zty, what are you doing ? Zty:                                     I want to calculate N!...... WhereIsHeroFrom:             So easy! How big N is ? Zty:                                    1 <=N <=1000000000000000000000000000000000000000000000… WhereIsHeroFrom:             Oh! You must be crazy! Are you Fa Shao? Zty:                                     No. I haven's finished my saying. I just said I want to calculate N! mod 2009 Hint : 0! = 1, N! = N*(N-1)!
 
 
Input
Each line will contain one integer N(0 <= N<=10^9). Process to end of file.
 
 
Output
For each case, output N! mod 2009
 
 
Sample Input

   
   
   
   

    
    
    
    4 5
   
   
   
   

 
 
Sample Output

   
   
   
   

    
    
    
    24 120
   
   
   
   

 
試合後の清題、チームを組んで試合の第1試合、ひざまずいた!!!
 
この問題は同余定理を考査しているが,無理にやるとタイムアウトして枝を切るわけにはいかない.
 
注意:この問題で使用する同余定理の公式は:(n*m)%c=(n%c*m%c)%c
 
一、テーマはnの階乗対2009の余剰を求めるので、つまり2009以上の数の階乗対2009の余剰はすべて0に等しいことを知っていて、だから以下のプログラムがあります:
 

#include<cstdio>
int main()
{
	int n,i,ans;
	while(scanf("%d",&n)!=EOF)
	{
		ans=1;
		if(n>=2009)
		  printf("0
");
		else
		{
			for(i=2;i<=n;i++)
				ans=(ans*(i%2009))%2009;
			printf("%d
",ans);
		}
	}
	return 0;
}

 
二、2009=41*7*7、すなわち、41以上の数の階乗対2009の余剰はすべてゼロに等しく、時間の複雑度は再び減少し、コードは以下の通りであることがわかる.
 

#include<cstdio>
int main()
{
	int n,i,ans;
	while(scanf("%d",&n)!=EOF)
	{
		ans=1;
		if(n>=41)
		  printf("0
");
		else
		{
			for(i=2;i<=n;i++)
				ans=(ans*(i%2009))%2009;
			printf("%d
",ans);
		}
	}
	return 0;
}