1230 - MODEX
Modular Arithmetic for Beginners
Topic: Binary Exponentiation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ///Binary Exponentiation | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define MAX 10005 | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| // compute x^n mod m | |
| ll binpow(ll a, ll b, ll m) | |
| { | |
| a %= m; | |
| ll res = 1; | |
| while(b > 0) | |
| { | |
| if(b & 1) | |
| res = (res * a) % m; | |
| a = (a * a) % m; | |
| b >>= 1; | |
| } | |
| return res; | |
| } | |
| int main() | |
| { | |
| FASTIO | |
| ///* | |
| //double start_time = clock(); | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| int t; | |
| cin >> t; | |
| while(t--) | |
| { | |
| ll x, y, m; | |
| cin >> x >> y >> m; | |
| cout << binpow(x, y, m) << endl; | |
| } | |
| int c; | |
| cin >> c; | |
| //double end_time = clock(); | |
| //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); | |
| return 0; | |
| } |
No comments:
Post a Comment