zerojudge d122. Oh! My Zero!!

千萬別用暴力解（１ａ和２ａ的解法）！！，因為一定會ＴＬＥ。
千萬別用２ｂ！！，因為輸入很大（長整數），這樣字要用很大的記憶體，會出現錯誤（ＲＥ），我試過，真的。

解法大全：

１．依思路分：

ａ）直接算階乘

ｂ）算５法

２．建表

ａ）建階乘表

ｂ）建５表

千萬別用暴力解（１ａ和２ａ的解法）！！，因為一定會ＴＬＥ。
千萬別用２ｂ！！，因為輸入很大（長整數），這樣字要用很大的記憶體，會出現錯誤（ＲＥ），我試過，真的。

思路：

數學歸納法

１．

首先，你要先了解１０＝２＊５，且２出現的次數比５多

所以要算出現比較少的次數（５的次數）

２．

再來你得先寫兩個表格

分別為，

ａ）５的倍數數字的質因數中有多少的５（５的倍數數字可以整除幾次５）

用數學式表示：ｎ＝ｋ＊５^ｍ　（ｋ，ｍ為正整數）

ｂ）輸入和輸出的關係

３．

找規律

我的解法：

先用這方式寫

２ｂ）先建表（１～１００００００中能被５整除的次數），在逐項加起來

#define PO 7
const int  MX=pow(10.0,PO);//because n is too large
// MX=pow(10.0,5);
typedef long long int LLI;
int five_n[MX]={0};

void print(int *,int );
void build()
{
	//memset(five_n,0,sizeof(five_n));
	for(int i=1;i<=PO;i++)
	{
		int n=pow(5.0,i);
		for(int  j=n;j<=MX;j+=n)
		{
			five_n[j]++;
		}		
	}
	return ;
}
int deal(LLI n)
{
	int sum=0;
	for(int i=5;i<=n;i+=5)
	{
		sum+=five_n[i];
	}	
	return sum;
}

RE (SIGSEGV)

１ｂ）算５法：就是輸入一個數字Ｎ，算Ｎ！可以被５除多少次

因為末位數是０或５的才能被５整除

因為Ｎ！＝１＊２＊３＊４＊５＊．．．＊Ｎ

只要算１～Ｎ中末位數是０或５的數字可以被５整除的次數，加起來就是答案

但是我發現一個規律，５可以被５整除１次，１０是１次，２５是兩次

在１～Ｎ中有Ｎ／５個是５的倍數，有Ｎ／２５個是２５個倍數

ans=in/5+in/25+in/125+...

所以我可以化簡成：

                int ans=0;
		LLI n=1;
		for(int i=1;n<=in;i++)
		{
			n=pow(5.0,i);
			ans+=in/n;	
		}		
		cout<<ans<<endl;

//or

                int ans=0;
		LLI n=1;
		for(int i=1;n<=in;i++)
		{
			n*=5;
			ans+=in/n;	
		}		
		cout<<ans<<endl;

//AC (2ms, 312KB)

註：

因為這題比較難，所以有不懂的可以在下面留言

還有我沒寫所有的方法，若有新解法（請先測試），可以在下面留言

也要謝謝別人的解題報告，它提供我一些想法

Search This Blog

zerojudge