結果
問題 |
No.3133 法B逆元
|
ユーザー |
|
提出日時 | 2025-05-29 21:15:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 1,287 bytes |
コンパイル時間 | 4,410 ms |
コンパイル使用メモリ | 299,452 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-05-29 21:16:03 |
合計ジャッジ時間 | 5,472 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; using ll = long long; const ll mod = 1e9 + 7; const ll mod2 = 998244353; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll pow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll pow(ll a, ll b, ll c) { ll ans = 1; while (b) { if (b & 1) ans = (ans * a) % c; b >>= 1; a = (a * a) % c; } return ans; } void check(bool b) { if (b) cout << "Yes\n"; else cout << "No\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; // cin >> t; while (t--) { string n;ll b; cin>>n>>b; if (b==1){ cout<<0<<'\n'; return 0; } ll x=0; for (int i = 0; i < n.size(); ++i) { x*=10; x+=n[i]-'0'; x%=b; // cout<<x<<' '; } // cout<<'\n'; ll ans=0; while (ans<b && (x*ans)%b!=1)++ans; if (ans==b){ cout<<"NaN"<<'\n'; return 0; } cout<<ans<<'\n'; } return 0; }