C++：a-power b模數k

-1

a^b模數k 問題：編寫一個程序，計算模數k的b次冪。例如，如果你被要求計算2^6 mod 7;的2第六功率是64因而64模7是1C++：a-power b模數k

輸入規格 您將得到3個整數，a，b和k，其中b表示功率和k表示模數操作數和0≤b ≤1000和1 <（a和k）≤1000

輸出規格 顯示只是一個整數，其爲0，k-1之間。

採樣輸入我

樣本輸出我

#include <iostream> 
#include <math.h> 
using namespace std; 

int main(){ 
    int a, b, k, d; 
    cin >> a >> b >> k; 

    int poew = pow(a, b); 
    d = poew % k; 

    cout << d; 
}

它運行良好，但在測試用例5失敗;

Test Case 5: 
---------- input.txt ---------- 
50 34 31 

---------- pattern.txt ---------- 
28

來源

2015-05-09 o07l

'Pow'是一種採用浮點數的方法。你將不得不使用別的東西來保持整數精度。另外，50^34不適合'int'。 – Caramiriel

使用這個來避免溢出（a * b）mod k ==（（a mod k）*（b mod k））mod k –

'pow（）'返回一個'double'，其不精確可能是導致錯誤的原因。你正在接近錯誤的問題;提示：通過平方來查找Exponentiation，並利用模數的屬性。 – jadhachem

你可以用32位算術來做到這一點。你只需要減少模km每個相乘後，停止數字過於龐大：

int pow_mod_k (int a, int b, int k) { 
    int result = 1 ; 
    while (b--) { 
     result *= a ; 
     result %= k ; 
    } 
    return result ; 
}

由於jadhachem在評論中指出，可以讓這個快用平方階梯。但是對於這麼小的數字，這是不值得的。

來源

2015-05-09 10:50:19 TonyK

C++：a-power b模數k

回答

相關問題