結果

問題 No.3133 法B逆元
ユーザー Today03
提出日時 2025-05-02 21:27:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,302 bytes
コンパイル時間 3,460 ms
コンパイル使用メモリ 279,012 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-02 21:27:06
合計ジャッジ時間 4,195 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(),(x).end()
#define IO ios::sync_with_stdio(false),cin.tie(nullptr);
#define LB(v, x) (ll)(lower_bound(ALL(v),x)-(v).begin())
#define UQ(v) sort(ALL(v)),(v).erase(unique(ALL(v)),v.end())
#define REP(i, n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i, a, b) for(ll i=(ll)(a); (a)<(b) ? i<(b) : i>(b); i+=((a)<(b) ? 1 : -1))
#define chmax(a, b) ((a)<(b) ? ((a)=(b), 1) : 0)
#define chmin(a, b) ((a)>(b) ? ((a)=(b), 1) : 0)

template<typename T> using rpriority_queue=priority_queue<T,vector<T>,greater<T>>;
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;
using ld=long double; using ull=uint64_t; using LL=__int128_t;
using VI=vector<int>; using VVI=vector<VI>; using VL=vector<ll>; using VVL=vector<VL>;
using PL=pair<ll,ll>; using VP=vector<PL>; using WG=vector<vector<pair<int,ll>>>;



/**
 * @brief 拡張ユークリッドの互除法
 * @details
 * gcd(a,b) = gcd(b%a,a), gcd(b,0) = b と b%a + (b/a)*a = b を使う。
 * ax + by = g なる x,y を求めたい。
 * 今、(b%a)X + aY = g なる X, Y が分かっている。
 * (b%a)X = bX - (b/a)*a*X より、これを代入して、
 * bX - (b/a)*a*X + aY = g
 * a(Y-(b/a)*X) + bX = g
 */
tuple<LL,LL,LL> ExtGcd(LL a, LL b) {
    if(a==0) return {b,0,1};
    auto [g,s,t]=ExtGcd(b%a,a);
    return {g,t-(b/a)*s,s};
}

/// @brief mod 逆元
/// @brief a^(-1) (mod m)
/// @note gcd(a,m)=1 でない場合、-1 を返す。
LL ModInvGcd(LL a, LL m) {
    // ax = 1 (mod m) <-> ax+my = 1 (mod m)
    auto [g,x,y]=ExtGcd(a,m);
    if(g!=1) return-1;
    return (x+m)%m;
}


constexpr const LL LL0=0;
constexpr const LL LL1=1;
constexpr const LL INFLL=LL1<<120;

istream& operator>>(istream& is, LL& x) {
	int c=is.peek();
	while(c==' '||c=='\n') is.get(), c=is.peek();
	bool neg=false;
	if(c=='-') neg=true, is.get();
	x=0;
	while(isdigit(is.peek())) x=x*10+is.get()-'0';
	if(neg) x=-x;
	return is;
}

ostream& operator<<(ostream& os, LL x) {
	if(x<0) os<<'-', x=-x;
	if(x==0) return os<<'0';
	string s;
	while(x>0) s+=x%10+'0', x/=10;
    reverse(ALL(s));
	return os<<s;
}

//----------------------------------------------------------

int main() {
    LL N,B; cin>>N>>B;

    LL ans=ModInvGcd(N,B);

    if(ans==-1) cout<<"NaN"<<endl;
    else cout<<ans<<endl;
}
0