結果
問題 | No.1339 循環小数 |
ユーザー |
![]() |
提出日時 | 2021-01-15 23:01:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,375 ms / 2,000 ms |
コード長 | 2,043 bytes |
コンパイル時間 | 819 ms |
コンパイル使用メモリ | 100,224 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-26 17:09:11 |
合計ジャッジ時間 | 15,001 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
#include <iostream>#include <algorithm>#include <string>#include <vector>#include <cmath>#include <map>#include <queue>#include <iomanip>#include <set>#include <tuple>#define mkp make_pair#define mkt make_tuple#define rep(i,n) for(int i = 0; i < (n); ++i)#define all(v) v.begin(),v.end()using namespace std;typedef long long ll;const ll MOD=1e9+7;template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}ll mod_pow(ll a,ll n,ll mod){a%=mod;ll res=1;while(n>0){if(n&1) res=res*a%mod;a=a*a%mod;n>>=1;}return res;}// gcd(a,mod) = 1ll mod_inv(ll a,ll mod){ll b=mod,u=1,v=0;while(b){ll t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}u%=mod;if(u<0) u+=mod;return u;}// minimum x for a^x = b (mod)// gcd(a,mod) = 1// x > 0 [x >= 0]ll mod_log(ll a,ll b,ll mod){a%=mod;b%=mod;ll low=-1,high=mod;while(abs(high-low)>1){ll mid=(low+high)/2;if(mid*mid>=mod) high=mid;else low=mid;}//ll sqm=sqrt(mod)+1;ll sqm=high;map<ll,ll> apow;ll val=a;for(int r=1;r<sqm;r++){if(apow.count(val)==false) apow[val]=r;val=val*a%mod;}ll A=mod_pow(mod_inv(a,mod),sqm,mod);ll target=b;for(int q=0;q<=sqm;q++){if(target==1&&q>0) return q*sqm;else if(apow.count(target)){ll res=sqm*q+apow[target];if(res>0) return res;//return res;}target=target*A%mod;}return -1;}void solve(){ll N;cin>>N;ll base=10;if(N%2==0){while(N%2==0) N/=2;//N/=2;//base/=2;}if(N%5==0){while(N%5==0) N/=5;//N/=5;//base/=5;}//cout<<base<<" "<<N<<"\n";if(N==1){cout<<1<<"\n";return;}ll ans=mod_log(base,1,N);cout<<ans<<"\n";}int main(){cin.tie(0);ios::sync_with_stdio(false);int T;cin>>T;rep(i,T) solve();return 0;}