結果
問題 | No.1339 循環小数 |
ユーザー |
|
提出日時 | 2024-09-17 23:33:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 885 bytes |
コンパイル時間 | 2,042 ms |
コンパイル使用メモリ | 198,000 KB |
最終ジャッジ日時 | 2025-02-24 09:11:16 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;ll modpow(ll a,ll n,ll p){ll r=1;while(n>0){if(n%2)r=(r*a)%p;a=(a*a)%p;n/=2;}return r;}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);ll T;cin>>T;while(T--){ll N,an=1e18;cin>>N;while(N%2==0)N/=2;while(N%5==0)N/=5;if(N==1){cout<<1<<endl;continue;}vector<ll> P;ll CN=N;for(int p=2;p*p<=N;p++)if(N%p==0){P.push_back(p);while(N%p==0)N/=p;}if(N!=1)P.push_back(N);N=CN;for(auto p:P){N*=(p-1);N/=p;}for(ll p=1;p*p<=N;p++)if(N%p==0)for(ll e:{p,N/p})if(modpow(10,e,CN)==1)an=min(an,e);cout<<an<<endl;}}