結果
問題 | No.251 大きな桁の復習問題(1) |
ユーザー |
![]() |
提出日時 | 2015-07-25 00:06:27 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 13 ms / 5,000 ms |
コード長 | 1,496 bytes |
コンパイル時間 | 861 ms |
コンパイル使用メモリ | 83,036 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-17 17:17:21 |
合計ジャッジ時間 | 1,728 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <iostream> #include <vector> #include <cstdio> #include <sstream> #include <map> #include <string> #include <algorithm> #include <queue> #include <cmath> #include <set> using namespace std; #define MOD 129402307 long long rem(string X, long long Y){ long long b = 0; for(int i=0; i<X.size(); i++){ b *= 10; b += X[i] - '0'; b %= Y; } return b; } long long power_mod(long long x, long long y, long long mod){ long long ret = 1; while(y){ if(y&1) ret = (ret*x) % mod; x = (x*x) % mod; y >>= 1; } return ret; } //find k such that x^k = y (mod z) //x and z are co-prime //x^(aH-b) = y (mod z) //x^aH = y * x^b (mod z) long long baby_step_giant_step(long long x, long long y, long long z){ long long H = sqrt(z) + 1; set<pair<long long,long long>> S; for(long long i=0, w=y; i<H; i++, w=(w*x)%z){ S.insert({w,i}); } long long k = -1; long long x_H = power_mod(x, H, z); for(long long i=1, w=x_H; i<=H; i++, w=(w*x_H)%z){ auto itr = S.lower_bound({w+1, 0}); if(itr == S.begin()) continue; itr--; if(itr->first == w){ return H * i - itr->second; } } return k; } int main(){ string n,m; cin >> n >> m; if(n == "0"){ cout << 0 << endl; return 0; } if(m == "0"){ cout << 1 << endl; return 0; } long long x = rem(n, MOD); if(x == 0){ cout << 0 << endl; return 0; } long long ord = baby_step_giant_step(x, 1, MOD); long long y = rem(m, ord); long long ans = power_mod(x, y, MOD); cout << ans << endl; return 0; }