HDOJ 1163 Eddy's digital Roots（簡單數論）

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;
}