程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDOJ 1163 Eddy's digital Roots(簡單數論)

HDOJ 1163 Eddy's digital Roots(簡單數論)

編輯:C++入門知識

HDOJ 1163 Eddy's digital Roots(簡單數論)


 

求解思路:

現在分析一個問題,假設將十位數為a,個位數為b的一個整數表示為ab,則推導得
ab*ab = (a*10+b)*(a*10+b) = 100*a*a+10*2*a*b+b*b
根據上式可得:root(ab*ab) = a*a+2*a*b+b*b = (a+b)*(a+b);[公式一]
同理也可證得:root(ab*ab*ab) = (a+b)*(a+b)*(a+b);[公式二]
可以看出,N個相同整數的乘積總值的樹根 = 每一項元素的樹根的乘積


再設另外一個整數cd,且cd!=ab
ab*cd = (a*10+b)*(c*10+d) = 100*a*c+10*(a*d+b*c)+b*d
根據上式可得:root(ab*cd) = a*c+a*d+b*c+b*d = (a+b)*(c+d);[公式三]
可見,對於兩個不相同整數也成立。


最後將上面證得的結果一般化:
N個整數的乘積總值的數根 = 每個項元素的數根的乘積

提示:本題只需根據[公式三] 即可AC.

注:思路確實是公式二沒錯,但是中間過程采用公式二會溢出,所以必須通過公式三。(思想一樣)

【AC代碼】:

 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
/* run this program using the console pauser or add your own getch, system(pause) or input loop */

int getRoot(int n)
{
	while (n >= 10)
	{
		int sum = 0;
		while (n)
		{
			sum += n%10;
			n /= 10;
		}
		n = sum;
	}
	return n;
}

int main(int argc, char** argv) {
	
	//freopen(in.txt, r, stdin);
	//freopen(out.txt, w, stdout);
	int n = 0;
	while (cin >> n && n)
	{
		int root = getRoot(n);
		int i = 0, mul = 1;
		for (i = 0; i < n; i++)
			mul = getRoot(root*mul); 
		cout << getRoot(mul) << endl; 
	}
	return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved