結果
問題 | No.1409 Simple Math in yukicoder |
ユーザー |
![]() |
提出日時 | 2021-02-20 12:41:14 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 2,008 bytes |
コンパイル時間 | 12,001 ms |
コンパイル使用メモリ | 405,888 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-17 20:29:18 |
合計ジャッジ時間 | 35,245 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 58 |
ソースコード
fn read() -> Vec<(u64, u64)> {let mut s = String::new();use std::io::Read;std::io::stdin().read_to_string(&mut s).unwrap();let mut it = s.trim().split_whitespace();let t: usize = it.next().unwrap().parse().unwrap();assert!(t <= 1000);let mut ask = vec![(0u64, 0u64); t];for p in ask.iter_mut() {p.0 = it.next().unwrap().parse().unwrap();p.1 = it.next().unwrap().parse().unwrap();assert!(1 <= p.0 && p.0 <= 1000);assert!(1 <= p.1 && p.1 <= 1000);assert!(is_prime(p.0 * p.1 + 1));}ask}fn is_prime(n: u64) -> bool {(2..).take_while(|p| p * p <= n).all(|p| n % p != 0)}fn pow(mut r: u64, mut n: u64, m: u64) -> u64 {let mut t = 1 % m;r %= m;while n > 0 {if n & 1 == 1 {t = t * r % m;}r = r * r % m;n >>= 1;}t}fn main() {let ask = read();for (v, x) in ask {let p = v * x + 1;if p == 2 {println!("1");continue;}let mut phi = p - 1;let mut f = vec![];for k in 2.. {if k * k > phi {break;}if phi % k == 0 {f.push(k);while phi % k == 0 {phi /= k;}}}if phi > 1 {f.push(phi);}let phi = p - 1;for z in 2.. {let mut ok = true;for f in f.iter() {ok &= pow(z, phi / *f, p) > 1;}if ok {let mut ans = (0..x).map(|i| pow(z, i * v, p)).collect::<Vec<_>>();ans.sort();for (i, a) in ans.iter().enumerate() {if i > 0 {print!(" ");}print!("{}", *a);}println!();break;}}}}