This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/discrete_logarithm_mod #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../mod/log.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int t; cin>>t; while(t--){ int x,y,m; cin>>x>>y>>m; int l=mod_log(x,y,m); if(l==m) l=-1; cout<<l<<"\n"; } cout<<flush; return 0; }
#line 1 "test/yosupo/discrete_logarithm_mod.test.cpp" // verification-helper: PROBLEM https://judge.yosupo.jp/problem/discrete_logarithm_mod #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "mod/log.cpp" #line 3 "mod/log.cpp" using namespace std; #endif //BEGIN CUT HERE // find x s.t. a^x = b (x >= 0) // return MOD if not found // MOD can be composite numbers template<typename T> T mod_log(T a,T b,const T MOD){ using ll = long long; ll g=1; { ll m=MOD; while(m){ g=(ll)g*a%MOD; m>>=1; } } g=__gcd(g,(ll)MOD); ll c=0,t=1; while(t%g){ if(t==b) return c; t=t*a%MOD; c++; } // not found if(b%g) return MOD; t/=g;b/=g; const ll n=MOD/g; ll h=0,gs=1; while(h*h<n){ gs=gs*a%n; ++h; } unordered_map<ll, ll> bs; { ll s=0,e=b; while(s<h){ e=e*a%n; bs[e]=++s; } } { ll s=0,e=t; while(s<n){ e=e*gs%n; s+=h; if(bs.count(e)) return c+s-bs[e]; } } // not found return MOD; } //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 8 "test/yosupo/discrete_logarithm_mod.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int t; cin>>t; while(t--){ int x,y,m; cin>>x>>y>>m; int l=mod_log(x,y,m); if(l==m) l=-1; cout<<l<<"\n"; } cout<<flush; return 0; }