結果
問題 | No.3133 法B逆元 |
ユーザー |
|
提出日時 | 2025-05-02 21:25:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 699 bytes |
コンパイル時間 | 1,991 ms |
コンパイル使用メモリ | 192,492 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-05-02 21:25:22 |
合計ジャッジ時間 | 2,815 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long eazymod(long long a,long long m){a %= m; if(a < 0) a += m; return a;} pair<long long,long long> invgcd(long long a,long long b){ //return {gcd(a,b),x} (xa≡g(mod b)) a = eazymod(a,b); if(a == 0) return {b,0}; long long x = 0,y = 1,memob = b; while(a){ long long q = b/a; b -= a*q; swap(x,y); y -= q*x; swap(a,b); } if(x < 0) x += memob/b; return {b,x}; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); unsigned long long N,B; cin >> N >> B; auto [g,ans] = invgcd(N%B,B); if(g == 1) cout << ans << endl; else cout << "NaN" << endl; }