This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub mugen1337/procon
#define PROBLEM "https://judge.yosupo.jp/problem/discrete_logarithm_mod" #include "./template.hpp" #include "../Math/log_mod.hpp" void solve(){ ll a,b,m;cin>>a>>b>>m; ll k=log_mod(a,b,m); cout<<k<<endl; // cout<<"a^res "<<pow_mod(a,k,m)<<" =? "<<b<<endl; } signed main(){ int q;cin>>q; while(q--) solve(); return 0; }
#line 1 "test/yosupo_DiscreteLog.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/discrete_logarithm_mod" #line 1 "template.hpp" #include<bits/stdc++.h> using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 1000000007 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" "); return os; } template<typename T> istream &operator>>(istream &is,vector<T>&v){ for(T &x:v)is>>x; return is; } #line 4 "test/yosupo_DiscreteLog.test.cpp" #line 1 "Math/inv_mod.hpp" ll inv_mod(ll a,ll m){ ll b=m,u=1,v=0,t; while(b){ t=a/b; swap(a-=t*b,b);swap(u-=t*v,v); } u%=m; if(u<0) u+=m; return u; } #line 1 "Math/pow_mod.hpp" // a^n (mod m) ll pow_mod(ll a,ll n,ll m){ ll ret=1; while(n){ if(n&1) ret=ret*a%m; a=(a*a)%m; n/=2; } return ret; } #line 3 "Math/log_mod.hpp" // https://qiita.com/suisen_cp/items/d597c8ec576ae32ee2d7 // 最小の非負整数xを返す // a ^ x = b mod m ll log_mod(ll a,ll b,ll m){ auto BSGS=[](ll a,ll b,ll m){ ll sq_m=sqrt(m)+1; // baby-step unordered_map<ll,ll> bs; ll bab=1; for(int i=0;i<sq_m;i++,bab=bab*a%m)if(!bs.count(bab)) bs[bab]=i; // giant-step ll a_m=pow_mod(inv_mod(a,m),sq_m,m); ll gia=b; for(int i=0;i<=sq_m;i++,gia=gia*a_m%m)if(bs.count(gia)) return sq_m*i+bs[gia]; return -1ll; }; function<ll(ll,ll,ll)> decomp_BSGS=[&decomp_BSGS, &BSGS](ll a,ll b,ll m){ a%=m,b%=m; if(m==1) return 0ll; if(b==1) return 0ll; ll g=gcd(a,m); if(g==1) return BSGS(a,b,m); if(b%g) return -1ll; m/=g; b=(b/g)*inv_mod(a/g,m); ll res=decomp_BSGS(a,b,m); if(res<0) return -1ll; return res+1; }; return decomp_BSGS(a,b,m); } #line 6 "test/yosupo_DiscreteLog.test.cpp" void solve(){ ll a,b,m;cin>>a>>b>>m; ll k=log_mod(a,b,m); cout<<k<<endl; // cout<<"a^res "<<pow_mod(a,k,m)<<" =? "<<b<<endl; } signed main(){ int q;cin>>q; while(q--) solve(); return 0; }