HDU 1163 Eddy's digital Roots(解法二)【高速モードべき乗+九余数定理】

質問リンク:HDU 1163 Eddy's digital Roots.
質問の簡単な説明:上記のリンクを参照してください.
問題分析:n^nの数本を計算するには、1つは速く、2つは簡単です.高速モードべき乗計算を用いて,数論における九余数の定理を加えると完璧である.
プログラム説明:(略)
参考リンク:HDU 1163 Eddy's digital Roots
題記:(略)
ACのC++言語プログラムは以下の通りである.

/* HDU1163 Eddy's digital Roots */

#include 

using namespace std;

const int NICE = 9;

//         
int powermod(int a, int n, int m)
{
    int res = 1;
    while(n) {
        if(n & 1) {        // n % 2 == 1
            res *= a;
            res %= m;
        }
        a *= a;
        a %= m;
        n >>= 1;
    }
    return res;
}

int main()
{
    int n, ans;

    while(cin >> n && n) {
        ans = powermod(n, n, NICE);
        cout << (ans ? ans : 9) << endl;
    }

    return 0;
}

転載先:https://www.cnblogs.com/tigerisland/p/7563705.html