UVA 10162 - Last Digit

included in 作業筆記演算法 UVA C++

2019-05-17 181 words One minute

Contents

本題為中山大學高等程式設計課程作業指定題目之四星題。

題目大意

給一個整數 N，輸出 1 + 2^2 + 3^3 + … + N^N 的結果的個位數。

輸入範圍

1 <= N <= 2 * (10 ^ 100)

解法

數字範圍很大，輸入先記得是 string。

再來可以用數學推或是簡單寫一段程式，找到循環節為 100，這個部份在我程式碼註解的地方。

最後就是處理一下字串，由於循環節為 100，所以我們只需要在意最後兩個數字，找到後輸出即可。

程式碼

        
        
        
    
#include <iostream>
using namespace std;
int pow(long a, long long b) {
    if (b == 0) return 1;
    return b % 2 ? (a * pow(a % 10, b-1) % 10) : pow((a * a) % 10, b/2);
}
int main(int argc, char *argv[]) {
    /*
    int table[10001] = {0}, n;
    bool find = false;
    for(int i=1; i<=10000; i++) {
    	table[i] = (table[i-1] + pow(i, i)) % 10;
    }
    for(n=1; !find; n++) {
    	for(int i=1; i<=n; i++, find=true) {
    		if (table[i] != table[i+n]) {
    			find = false;
    			break;
    		}
    	}
    }
    cout << n-1 << endl;
    */
    int table[101] = {0};
    for(int i=1; i<=100; i++) table[i] = (table[i-1] + pow(i, i)) % 10;
    string N;
    while(cin >> N && N != "0") {
    	int n = N.back() - '0';
        if (N.size() > 1) n += (N[N.size()-2] - '0') * 10;
        cout << table[n] << endl;
    }
    return 0;
}