結果
問題 | No.1339 循環小数 |
ユーザー |
👑 ![]() |
提出日時 | 2021-01-15 22:07:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 526 ms / 2,000 ms |
コード長 | 645 bytes |
コンパイル時間 | 2,359 ms |
コンパイル使用メモリ | 200,320 KB |
最終ジャッジ日時 | 2025-01-17 19:31:03 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:22:15: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 22 | int T; scanf("%d",&T); | ~~~~~^~~~~~~~~ main.cpp:24:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 24 | ULL N; scanf("%llu",&N); | ~~~~~^~~~~~~~~~~
ソースコード
#include<bits/stdc++.h>using namespace std;using LL=long long;using ULL=unsigned long long;#define rep(i,n) for(int i=0; i<(n); i++)ULL loop(ULL N){while(N%2==0) N/=2;while(N%5==0) N/=5;if(N==1) return 1;unordered_map<ULL,ULL> X(30000);ULL p=1;rep(i,30000){ X[p]=i; p=p*10%N; if(p==1) return i+1; }p=1;ULL inv=0; for(ULL i=1; i<10; i++) if(N*i%10==9) inv=(N*i+1)/10;ULL q=1; rep(i,30000) q=q*inv%N;rep(i,40000){ p=p*q%N; if(X.count(p)) return (i+1)*30000+X[p]; }return ~0ull;}int main(){int T; scanf("%d",&T);while(T--){ULL N; scanf("%llu",&N);printf("%llu\n",loop(N));}return 0;}