結果
問題 |
No.1339 循環小数
|
ユーザー |
|
提出日時 | 2023-11-01 13:54:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 850 bytes |
コンパイル時間 | 1,970 ms |
コンパイル使用メモリ | 192,380 KB |
最終ジャッジ日時 | 2025-02-17 17:15:34 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; namespace Lib{ ll modpow(long long a,int n,int const mod){ long long ret=1,t=a; while(n>0){ if(n&1)ret=ret*t%mod; t=t*t%mod; n/=2; } return ret; } } void solve(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int test_case; cin>>test_case; while (test_case--){ solve(); } } void solve(){ int N; cin>>N; while(N%2==0)N/=2; while(N%5==0)N/=5; int t=N,d=N; for(int i=2;i*i<=d;i++){ if(d%i==0){ while(d%i==0)d/=i; t=t/i*(i-1); } } if(d!=1){ t=t/d*(d-1); } int ans=t; for(int i=1;i*i<=t;i++){ if(t%i==0){ if(Lib::modpow(10,i,N)==1){ ans=min(ans,i); } if(Lib::modpow(10,t/i,N)==1){ ans=min(ans,t/i); } } } cout<<ans<<'\n'; }