代碼中需要澄清以及底層數學是什麼？

需要解決的問題，以計算代碼中需要澄清以及底層數學是什麼？

a^b mod p where a,b <= 10^100000 
MOD = 1000000007

在每個測試用例a和b給出如下上述限制的數字串。我試圖用指數調製使用下面提到的代碼來解決它。

typedef long long ll; 
ll modPow(ll base, ll exp, ll n) { 
    base = base%n; 
    if (exp == 0) 
     return 1; 
    else if (exp == 1) 
     return base; 
    else if (exp % 2 == 0) 
     return modPow(base * base % n, exp/2, n); 
    else 
     return base * modPow(base, exp - 1, n) % n; 
} 

int main() { 
    ll test, i, j , k; 
    string a, b; 
    ll x, y, ans; 
    cin >> test ; 
    while (test--) { 
     cin >> a >> b; 
     x = 0; 
     for (i = 0; i < a.length(); i++) 
      x = (x * 10 + (a[i] - '0')) % MOD; 
     y = 0 ; 

     for (i = 0 ; i < b.length(); i++) 
      y = (y * 10 + (b[i] - '0')) % (MOD - 1); 

     // cout << x <<" "<< y << endl; 
     ans = modPow(x, y, MOD); 
     cout << ans % MOD << endl ; 
    } 
}

我只是想知道，在計算指數值y，爲什麼我們做的

for (j = 0; j < b.length(); j++) 
    y = ((y * 10) + (b[i] - '0')) % (MOD-1); // gave correct answer

代替

for (j = 0; j < b.length(); j++) 
    y = ((y * 10) + (b[i] - '0')) % (MOD); // gave wrong answer

任何人都可以請澄清，並解釋其背後的數學？

Sample Test Case : 
INPUT : 
5 
3 2 
4 5 
7 4 
34534985349875439875439875349875 93475349759384754395743975349573495 
34543987529435983745230948023948 3498573497543987543985743989120393097595572309482304 

OUTPUT : 
9 
1024 
2401 
735851262 
985546465

來源

2014-02-25 Amit Kumar

看一看費馬小定理：http://en.wikipedia.org/ wiki/Fermat％27s_little_theorem –

這是錯誤的網站？拿走編程元素，這似乎與真正的問題無關，這似乎應該在http://math.stackexchange.com上 –

根據的推廣，

一個^b模p =一個^{b MOD（P-1）}模p

來源

2014-02-25 13:18:28 Anton

這是因爲一個^b MOD Ñ具有一個週期（至多）長度Ñ - 1.

2^n mod 5 --> 1 2 4 3 | 1 2 4 3 | 1 2 4 3 | ... (cycle of 4 with n = 0 ... 11) 
3^n mod 7 --> 1 3 2 6 4 5 | 1 3 2 6 4 5 | ... (cycle of 6)

因此，^ B mod N = a ^（b mod（N-1））mod N

來源

2014-02-25 13:15:34

代碼中需要澄清以及底層數學是什麼？

回答

相關問題