結果

問題 No.1339 循環小数
ユーザー srjywrdnprkt
提出日時 2023-08-24 23:06:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 1,578 bytes
コンパイル時間 2,096 ms
コンパイル使用メモリ 207,492 KB
最終ジャッジ日時 2025-02-16 13:20:39
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> factor;
map<ll, ll> prime;
void all_factor(ll n){
factor.clear();
for (ll i = 1; i*i <= n; i++){
if (n % i == 0){
factor.push_back(i);
if (i*i != n) factor.push_back(n / i);
}
}
sort(factor.begin(), factor.end());
}
void prime_factor(ll n){
prime.clear();
ll m = n;
if (n % 2 == 0){
while(n % 2 == 0){
prime[2]++;
n /= 2;
}
}
for (ll i = 3; i*i <= m; i+=2){
if (n % i == 0){
while(n % i == 0){
prime[i]++;
n /= i;
}
}
}
if (n != 1){
prime[n]++;
}
}
ll mod_exp(ll b, ll e, ll m){
if (e > 0 && b == 0) return 0;
b %= m;
ll ans = 1;
while (e > 0){
if ((e & 1LL)) ans = (ans * b) % m;
e = e >> 1LL;
b = (b*b) % m;
}
return ans;
}
ll totient(ll N){
prime_factor(N);
ll res=1;
for (auto [p, e] : prime){
res *= mod_exp(p, e-1, 9e18) * (p-1);
}
return res;
}
void solve(){
ll N;
cin >> N;
while(N % 2 == 0) N /= 2;
while(N % 5 == 0) N /= 5;
ll t = totient(N);
all_factor(t);
if (N == 1){
cout << 1 << endl;
return;
}
for (auto x : factor){
if (mod_exp(10, x, N) == 1){
cout << x << endl;
return;
}
}
}
int main(){
int T;
cin >> T;
while(T){
T--;
solve();
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0