結果
問題 | No.551 夏休みの思い出(2) |
ユーザー | koba-e964 |
提出日時 | 2017-07-29 00:22:07 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 73 ms / 4,000 ms |
コード長 | 3,092 bytes |
コンパイル時間 | 13,524 ms |
コンパイル使用メモリ | 381,904 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-10 11:04:04 |
合計ジャッジ時間 | 14,875 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 3 ms
6,816 KB |
testcase_04 | AC | 5 ms
6,816 KB |
testcase_05 | AC | 10 ms
6,816 KB |
testcase_06 | AC | 13 ms
6,820 KB |
testcase_07 | AC | 1 ms
6,816 KB |
testcase_08 | AC | 1 ms
6,816 KB |
testcase_09 | AC | 1 ms
6,816 KB |
testcase_10 | AC | 2 ms
6,820 KB |
testcase_11 | AC | 1 ms
6,816 KB |
testcase_12 | AC | 1 ms
6,816 KB |
testcase_13 | AC | 1 ms
6,816 KB |
testcase_14 | AC | 1 ms
6,816 KB |
testcase_15 | AC | 2 ms
6,820 KB |
testcase_16 | AC | 1 ms
6,816 KB |
testcase_17 | AC | 1 ms
6,816 KB |
testcase_18 | AC | 2 ms
6,816 KB |
testcase_19 | AC | 1 ms
6,820 KB |
testcase_20 | AC | 1 ms
6,816 KB |
testcase_21 | AC | 1 ms
6,816 KB |
testcase_22 | AC | 2 ms
6,816 KB |
testcase_23 | AC | 1 ms
6,820 KB |
testcase_24 | AC | 1 ms
6,816 KB |
testcase_25 | AC | 2 ms
6,816 KB |
testcase_26 | AC | 2 ms
6,820 KB |
testcase_27 | AC | 56 ms
6,816 KB |
testcase_28 | AC | 53 ms
6,816 KB |
testcase_29 | AC | 48 ms
6,816 KB |
testcase_30 | AC | 63 ms
6,820 KB |
testcase_31 | AC | 46 ms
6,816 KB |
testcase_32 | AC | 59 ms
6,816 KB |
testcase_33 | AC | 55 ms
6,816 KB |
testcase_34 | AC | 48 ms
6,816 KB |
testcase_35 | AC | 48 ms
6,816 KB |
testcase_36 | AC | 52 ms
6,820 KB |
testcase_37 | AC | 57 ms
6,820 KB |
testcase_38 | AC | 59 ms
6,820 KB |
testcase_39 | AC | 55 ms
6,816 KB |
testcase_40 | AC | 58 ms
6,816 KB |
testcase_41 | AC | 73 ms
6,816 KB |
testcase_42 | AC | 55 ms
6,820 KB |
testcase_43 | AC | 54 ms
6,820 KB |
testcase_44 | AC | 54 ms
6,820 KB |
testcase_45 | AC | 53 ms
6,820 KB |
testcase_46 | AC | 55 ms
6,816 KB |
testcase_47 | AC | 2 ms
6,820 KB |
testcase_48 | AC | 1 ms
6,820 KB |
コンパイルメッセージ
warning: unused variable: `r` --> src/main.rs:94:9 | 94 | let r: i64 = get(); | ^ help: if this is intentional, prefix it with an underscore: `_r` | = note: `#[warn(unused_variables)]` on by default
ソースコード
#[allow(unused_imports)] use std::cmp::*; #[allow(unused_imports)] use std::collections::*; use std::io::Read; #[allow(dead_code)] fn getline() -> String { let mut ret = String::new(); std::io::stdin().read_line(&mut ret).ok().unwrap(); ret } fn get_word() -> String { let mut stdin = std::io::stdin(); let mut u8b: [u8; 1] = [0]; loop { let mut buf: Vec<u8> = Vec::with_capacity(16); loop { let res = stdin.read(&mut u8b); if res.unwrap_or(0) == 0 || u8b[0] <= b' ' { break; } else { buf.push(u8b[0]); } } if buf.len() >= 1 { let ret = String::from_utf8(buf).unwrap(); return ret; } } } #[allow(dead_code)] fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() } /** * p is prime */ fn modsqrt(mut a: i64, p: i64) -> Option<i64> { a %= p; if a == 0 { return Some(0); } if p == 2 { return Some(a); } if powmod(a, (p - 1) / 2, p) != 1 { return None; } let mut b = 1; while powmod(b, (p - 1) / 2, p) == 1 { b += 1; } let mut e = 0; let mut m = p - 1; while m % 2 == 0 { m /= 2; e += 1; } let mut x = powmod(a, (m - 1) / 2, p); let mut y = a * (x * x % p) % p; x = x * a % p; let mut z = powmod(b, m, p); while y != 1 { let mut j = 0; let mut t = y; while t != 1 { j += 1; t = t * t % p; } assert!(j < e); z = powmod(z, 1 << (e - j - 1), p); x = x * z % p; z = z * z % p; y = y * z % p; e = j; } Some(x) } fn powmod(x: i64, mut e: i64, m: i64) -> i64 { let mut sum = 1; let mut cur = x % m; while e > 0 { if e % 2 != 0 { sum = sum * cur % m; } cur = cur * cur % m; e /= 2; } sum } fn solve() { let p: i64 = get(); let r: i64 = get(); let q = get(); for _ in 0 .. q { let a: i64 = get(); let b: i64 = get(); let c: i64 = get(); let b = b * powmod(a, p - 2, p) % p; let c = c * powmod(a, p - 2, p) % p; let ss = modsqrt((b * b + (2 * p - 4) * c) % p, p); match ss { Some(ss) => { let mut hs = Vec::new(); hs.push(((2 * p - b - ss) % p) * powmod(2, p - 2, p) % p); hs.push(((p - b + ss) % p) * powmod(2, p - 2, p) % p); hs.sort(); if hs[0] == hs[1] { println!("{}", hs[0]); } else { println!("{} {}", hs[0], hs[1]); } }, None => { println!("-1"); }, } } } fn main() { // In order to avoid potential stack overflow, spawn a new thread. let stack_size = 104_857_600; // 100 MB let thd = std::thread::Builder::new().stack_size(stack_size); thd.spawn(|| solve()).unwrap().join().unwrap(); }