結果
問題 | No.3133 法B逆元 |
ユーザー |
|
提出日時 | 2025-05-02 22:14:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,691 bytes |
コンパイル時間 | 1,753 ms |
コンパイル使用メモリ | 194,476 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-05-02 22:14:43 |
合計ジャッジ時間 | 2,621 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define mod99 998244353 #define mod107 1000000007 #define endl "\n" #define rep(i,n) for (int i = 0; (i) < (n); ++i) #define prep(i,a,n) for (int i = (a); i < (n); ++i) #define rrep(i,n) for (int i = n-1; i >= 0; --i) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(), a.rend() #define si(x) ((int)(x).size()) //#define YN(bool) if(bool){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;} #define yn(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;} #define PRE(x) cout << fixed << setprecision(x) #define YES cout << "Yes\n" #define NO cout << "No\n" template <typename T> inline T gcd(T a,T b) {return (b==0)?a:gcd(b,a%b);} template <typename T> inline T lcm(T a, T b) {return a/gcd(a,b)*b;} template<class T>bool chmax(T &a, T b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, T b) { if (b<a) { a=b; return 1; } return 0; } int dx[4]={1,0,-1,0};int dy[4]={0,1,0,-1};using ull = unsigned long long; string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; //string abc = "abcdefghijklmnopqrstuvwxyz"; bool issubsquence(string s,string t){ ll i=0; for(char c:t){ if(i<si(s)&&s[i]==c) i++; } return i==si(s); } using i128 = __int128; i128 pgcd(i128 a,i128 b,i128 &x, i128 &y) { if(b==0) {x=1;y=1;return a;} i128 d = pgcd(b,a%b,y,x); y -= a/b*x; return d; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s;cin >> s; ll b;cin >> b; i128 n = 0; for(char c:s) n = n*10+(c-'0'); i128 x, y; i128 p = pgcd(n,b,x,y); if(p!=1) {cout << "NaN" << endl; return 0;} else {ll i=(x%b+b)%b; cout << i << endl; return 0;} cout << "NaN" << endl; }