結果
問題 | No.2191 一元二次式 mod 奇素数 |
ユーザー |
![]() |
提出日時 | 2023-01-13 22:37:52 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 3,202 bytes |
コンパイル時間 | 18,666 ms |
コンパイル使用メモリ | 388,448 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 18:25:53 |
合計ジャッジ時間 | 19,994 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
fn main() {input!(p: u64);let k = (p - 1) / 2;let r = (1 + 2 * p - 16 * k % p - 4 * k * k % p) % p;let ans = if pow_mod(r, (p - 1) / 2, p) == 1 {"YES"} else {"NO"};println!("{}", ans);}fn pow_mod(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}mod util {pub trait Join {fn join(self, sep: &str) -> String;}impl<T, I> Join for IwhereI: Iterator<Item = T>,T: std::fmt::Display,{fn join(self, sep: &str) -> String {let mut s = String::new();use std::fmt::*;for (i, v) in self.enumerate() {if i > 0 {write!(&mut s, "{}", sep).ok();}write!(&mut s, "{}", v).ok();}s}}}// ---------- begin input macro ----------// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8#[macro_export]macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}#[macro_export]macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}#[macro_export]macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, bytes) => {read_value!($iter, String).bytes().collect::<Vec<u8>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}// ---------- end input macro ----------// floor(a ^ (1 / k))pub fn kth_root(a: u64, k: u64) -> u64 {assert!(k > 0);if a == 0 {return 0;}if k >= 64 {return 1;}if k == 1 {return a;}let valid = |x: u64| -> bool {let mut t = x;for _ in 1..k {let (val, ok) = t.overflowing_mul(x);if !(!ok && val <= a) {return false;}t = val;}true};let mut ok = 1;let mut ng = 2;while valid(ng) {ok = ng;ng *= 2;}while ng - ok > 1 {let mid = ok + (ng - ok) / 2;if valid(mid) {ok = mid;} else {ng = mid;}}ok}