匯東網


NOJ - T012

[編輯] [转简体]
|
作者:huidong | 分類:【編程】NOJ 和 C 程序設計習題
[ 11 瀏覽 0 評論 3 贊 3 踩 ]

概要
快速冪算法

正文

#include <stdio.h>
#include <math.h>

int main()
{
    // 由於輸入爲正整數,且最大取到 2^63 故用 llu
    // ans 存儲最終結果
    unsigned long long a, b, m, ans = 1;
    scanf("%llu %llu %llu", &a, &b, &m);

    while (b)
    {
        if (b & 1)
            ans = (ans * a) % m;    // 根據 b 的當前位是否爲 1 確定 ans 這一循環是否需要乘入 a,
                                    // 乘完之後立即取模,答案不變

        a = (a * a) % m;            // 每次循環 a 變成 (a^2) % m,這是最快也是最省空間的辦法
        b >>= 1;                    // 按位閱讀 b
    }

    printf("%llu", ans);

    return 0;
}

代碼筆記


[ 3] [ 3]


 評論區  0 條評論

+ 添加評論