結果
問題 | No.1339 循環小数 |
ユーザー |
![]() |
提出日時 | 2021-01-16 00:57:25 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 2,752 bytes |
コンパイル時間 | 13,771 ms |
コンパイル使用メモリ | 381,904 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-26 19:04:33 |
合計ジャッジ時間 | 14,254 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
use std::io::{Read, Write};struct Scanner<R> { bytes: std::io::Bytes<R>, buf: Vec<u8> }impl<R: Read> Scanner<R> {fn new(r: R) -> Scanner<R> {Scanner { bytes: r.bytes(), buf: Vec::new() }}fn next(&mut self) -> &str {self.buf = {self.bytes.by_ref().map(|b| b.unwrap()).skip_while(|b| b.is_ascii_whitespace()).take_while(|b| !b.is_ascii_whitespace()).collect::<Vec<_>>()};unsafe { std::str::from_utf8_unchecked(&self.buf) }}}macro_rules! scan {($sc:expr, [$t:tt; $n:expr]) => ((0..$n).map(|_| scan!($sc, $t)).collect::<Vec<_>>());($sc:expr, ($($t:tt),*)) => (($(scan!($sc, $t)),*));($sc:expr, Usize1) => (scan!($sc, usize) - 1);($sc:expr, Bytes) => ($sc.next().bytes().collect::<Vec<_>>());($sc:expr, Chars) => ($sc.next().chars().collect::<Vec<_>>());($sc:expr, $t:ty) => ($sc.next().parse::<$t>().unwrap());}fn prime_factorize(mut n: usize) -> Vec<(usize, usize)> {let mut res = Vec::new();for i in 2.. {if i * i > n { break; }let mut cnt = 0;while n % i == 0 {cnt += 1;n /= i;}if cnt > 0 { res.push((i, cnt)); }}if n > 1 { res.push((n, 1)); }res}fn euler_f(n: usize) -> usize {prime_factorize(n).iter().fold(n, |acc, (i, _)| acc * (i - 1) / i)}fn get_divisors(n: usize) -> Vec<usize> {let (mut a, mut b) = (Vec::new(), Vec::new());for i in (1..).take_while(|i| i * i <= n) {if n % i > 0 { continue; }a.push(i);let j = n / i;if j == i { continue; }b.push(j);}a.into_iter().chain(b.into_iter().rev()).collect::<Vec<_>>()}fn run<R: Read, W: Write>(mut sc: Scanner<R>, mut wr: W) {let pow_mod = |mut a: usize, mut n: usize, m: usize| -> usize {let mut res = 1;while n > 0 {if n & 1 > 0 {res = res * a % m;}a = a * a % m;n >>= 1;}res};for _ in 0..scan!(sc, usize) {let mut n = scan!(sc, usize);while n % 2 == 0 { n /= 2; }while n % 5 == 0 { n /= 5; }if n == 1 {writeln!(wr, "1").ok();continue;}let m = euler_f(n);for i in get_divisors(m) {if pow_mod(10, i, n) == 1 {writeln!(wr, "{}", i).ok();break;}}}}fn main() {let (stdin, stdout) = (std::io::stdin(), std::io::stdout());let sc = Scanner::new(std::io::BufReader::new(stdin.lock()));let wr = std::io::BufWriter::new(stdout.lock());run(sc, wr);}