結果
問題 | No.377 背景パターン |
ユーザー | koba-e964 |
提出日時 | 2021-11-21 20:24:57 |
言語 | Rust (1.77.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,216 bytes |
コンパイル時間 | 12,699 ms |
コンパイル使用メモリ | 382,172 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-23 02:42:03 |
合計ジャッジ時間 | 14,418 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
ソースコード
use std::io::Read; fn get_word() -> String { let stdin = std::io::stdin(); let mut stdin=stdin.lock(); 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() } fn factorize(mut x: i64) -> Vec<(i64, usize)> { let mut p = 2; let mut ans = vec![]; while p * p <= x { let mut e = 0; while x % p == 0 { x /= p; e += 1; } if e > 0 { ans.push((p, e)); } p += 1; } if x > 1 { ans.push((x, 1)); } ans } fn dfs(v: usize, pe: &[(i64, usize)], mut x: i64, mut phi: i64, ans: &mut Vec<(i64, i64)>) { if v >= pe.len() { ans.push((x, phi)); return; } let (p, e) = pe[v]; dfs(v + 1, pe, x, phi, ans); x /= p; phi *= p - 1; for _ in 0..e { dfs(v + 1, pe, x, phi, ans); x /= p; phi *= p; } } fn get_divs_and_phis(x: i64) -> Vec<(i64, i64)> { let pe = factorize(x); let mut ans = vec![]; dfs(0, &pe, x, 1, &mut ans); ans } fn powmod(x: i64, mut e: i64) -> i64 { let mut sum = 1; let mut cur = x % MOD; while e > 0 { if e % 2 != 0 { sum = sum * cur % MOD; } cur = cur * cur % MOD; e /= 2; } sum } const MOD: i64 = 1_000_000_007; fn main() { let h: i64 = get(); let w: i64 = get(); let k: i64 = get(); let hpe = get_divs_and_phis(h); let wpe = get_divs_and_phis(w); let mut ans = 0; for &(a, phi1) in &hpe { for &(b, phi2) in &wpe { let mut tmp = powmod(k, a * b); tmp = tmp * phi1 % MOD; tmp = tmp * phi2 % MOD; ans = (ans + tmp) % MOD; } } println!("{}", ans); }