指數

Question

http://z-trening.com/tasks.php?show_task=5000000069&lang=uk

#include <stdio.h> 

int main(void) 
{ 
    long long o, s, m, i; 
    long long rez = 1; 

    scanf("%lld %lld %lld", &o, &s, &m); 
    o = o % m; 
    for (i = 0; i < s; i++){ 
     rez = (rez * o) % m; 
    } 
    printf("%lld", rez); 
    return 0; 
} 

它爲10的20個任務。 有沒有更快的方法來提高o^s？

Answer 1

是的，有一個更快的方法：模冪運算。 http://en.wikipedia.org/wiki/Modular_exponentiation

重複乘法（您的算法）運行在指數時間，而模冪運算在多項式時間內運行。它的工作原理是這樣的：

比方說，你要計算A^B模M. 首先，在二進制寫B：

B = bn,bn-1,...,b1,b0 

這意味着，

B = bn * 2^n + bn-1 * 2^(n-1) + ... + b1 * 2 + b0 

代入在表達式A^B中：

A^B = A^(2^n)^bn * A^(2^(n-1))^bn-1 * ... * A^2^b1 * A^b0 

可以遞歸地計算A ^（2^n）：

A^(2^n) = (A^(2^(n-1)))^2 

現在，問題是，使用這種同一性計算A ^（2^i）對於每個重複使用我平方模M.乘法和冪保持模塊化算術的通常身份太多，所以這是完全合法的。完整的算法：

input: A,B,M 
output: A^B mod M 

result = 1 
while(B != 0){ 
    if(B is odd){ 
     result = result * A mod M 
    } 
    B = B/2 
    A = A * A mod M 
} 
return result 

Answer 2

一個簡單的方法，以減少計算量使用等式：

a^(b+c) = a^b*a^c  (1) 

和

(x*y)%z = ((x%z)*(y%z))%z (2) 

這兩個等式可以快速使用計算(o^1)%m，(o^2)%m ，(o^4)%m，(o^8)%m，...：

o2n = (on * on)%m 

的問題，現在可以用一個循環，一次每一位迭代中s，這意味着複雜性已經降低，從O(s)到O(log(s)解決。

long long s, o; 
int m; 

// Input s,o,m (code omitted) 

int res = 1, on = o%m; // Assuming int is at least 32 bits 
for (i = 0; i < 35; i++) { // 2^35 is larger than the largest s allowed. 
    if (s & 1 << i) { 
    res = res * on; 
    } 
    on = (on*on)%m; 
} 
printf("%d\n", res);