結果
問題 | No.1339 循環小数 |
ユーザー |
|
提出日時 | 2021-05-17 20:49:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 1,493 bytes |
コンパイル時間 | 3,665 ms |
コンパイル使用メモリ | 201,616 KB |
最終ジャッジ日時 | 2025-01-21 13:30:21 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
#include<bits/stdc++.h>using namespace std;vector<int> div_enum(int n){vector<int> res;for(int i=1;i*i<=n;++i){if(n%i!=0){continue;}res.push_back(i);if(i!=n/i){res.push_back(n/i);}}sort(res.begin(),res.end());return res;}vector<pair<int,int>> prime_fact(int n){vector<pair<int,int>> res;for(int i=2;i*i<=n;++i){if(n%i!=0){continue;}int exp=0;while(n%i==0){n/=i;exp+=1;}res.push_back({i,exp});}if(n!=1){res.push_back({n,1});}return res;}int power(int a,int b){int res=1;for(int i=0;i<b;++i){res*=a;}return res;}int euler_func(int n){auto vec=prime_fact(n);int res=1;for(size_t i=0;i<vec.size();++i){res*=power(vec[i].first,vec[i].second)-power(vec[i].first,vec[i].second-1);}return res;}int64_t pow_mod(int64_t a,int64_t n,int64_t mod){int64_t res=1,now=a;while(n){if(n&1){res=res*now%mod;}now=now*now%mod;n>>=1;}return res;}void solve(){int n;cin>>n;while(n%2==0){n/=2;}while(n%5==0){n/=5;}int Max=euler_func(n);auto vec=div_enum(Max);for(size_t i=0;i<vec.size();++i){if(pow_mod(10,vec[i],n)==1){cout<<vec[i]<<endl;return;}}cout<<1<<endl;return;}int main(){int T;cin>>T;for(int i=0;i<T;++i){solve();}return 0;}