[問題] 大數如何遞減?
開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
C++
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
問題(Question)：
我在寫CPE的一個題目，答案正確但執行時間太久...
題目是這樣的：
input為一系列的整數，範圍是1~2*10^100
對每個input假設為n
計算s=1^1+2^2+3^3+...+n^n
只取s的個位數作為答案
最後以0當作結束
例如:
input: output:
1 1
2 5
3 2
0
我的程式只把遞減的部分PO上來，因為計算總合的部份我寫的有點亂
怕影響各位閱讀
而主要時間應該也是花在遞減這方面
底下這個數字是題目給的最大的input，也是主要不通過的原因
餵入的資料(Input)：
655350
0
預期的正確結果(Expected Output)：
答案正確
錯誤結果(Wrong Output)：
答案正確
程式碼(Code)：(請善用置底文網頁, 記得排版)
http://ideone.com/BQz0Uz
補充說明(Supplement)：
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.19.145.249
推
01/21 21:13, , 1F
01/21 21:13, 1F
→
01/21 21:15, , 2F
01/21 21:15, 2F
→
01/21 21:58, , 3F
01/21 21:58, 3F
→
01/21 21:59, , 4F
01/21 21:59, 4F
推
01/22 04:02, , 5F
01/22 04:02, 5F
推
01/22 04:20, , 6F
01/22 04:20, 6F
n最大是2*10^100
655350是網站檢查我的程式對錯時用的其中一個input
int sum = 0;
bool flag;
do
{
string twodi;
if (num.size() != 1) //這邊取num的最低的兩位數
twodi = num.substr(num.size()-2);
else //如果只有一位數就取一位數
twodi = num.substr(num.size()-1);
istringstream strm(twodi);
int n, imp;
strm >> imp; //轉成int來計算
n=imp%10; //n是底數，只需要取個位數
imp = imp%4+4; //imp是指數，因為四次內會出現循環，+4是為了避免
int one = 1; //正好變成0
for (int i = 0; i != imp; i++) //one相當於num^num取個位數
{
one = one*n;
}
sum += one; //把num^num的個位數累加到sum，等待下次遞減後再存
sum = sum%10; //(num-1)^(num-1)，直到num=1
flag = 0;
.
.
.
.
}while (!num.empty()); //每離開do-while迴圈就處理完一個input
cout << sum << endl;
}
return 0;
}
※ 編輯: luke90512 來自: 163.19.145.249 (01/22 08:20)
→
01/22 08:37, , 7F
01/22 08:37, 7F
→
01/22 08:39, , 8F
01/22 08:39, 8F
討論串 (同標題文章)