結果
| 問題 | No.1200 お菓子配り-3 |
| ユーザー |
 akakimidori
|
| 提出日時 | 2020-08-28 22:20:00 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 166 ms / 4,000 ms |
| コード長 | 6,182 bytes |
| コンパイル時間 | 13,716 ms |
| コンパイル使用メモリ | 375,092 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-20 22:33:56 |
| 合計ジャッジ時間 | 16,601 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 31 |
コンパイルメッセージ
warning: unused variable: `i`
--> src/main.rs:127:15
|
127 | let mut i = r;
| ^ help: if this is intentional, prefix it with an underscore: `_i`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `i`
--> src/main.rs:128:11
|
128 | for i in 0..r {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
warning: variable does not need to be mutable
--> src/main.rs:127:11
|
127 | let mut i = r;
| ----^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable `B` should have a snake case name
--> src/main.rs:165:7
|
165 | let B = (6 * isqrt_rem(2 * s).0) as usize;
| ^ help: convert the identifier to snake case: `b`
|
= note: `#[warn(non_snake_case)]` on by default
warning: variable `D` should have a snake case name
--> src/main.rs:168:9
|
168 | let D = k * n;
| ^ help: convert the identifier to snake case: `d`
warning: variable `P_0` should have a snake case name
--> src/main.rs:169:10
|
169 | let (P_0, mut Q) = isqrt_rem(D);
| ^^^ help: convert the identifier to snake case: `p_0`
warning: variable `Q` should have a snake case name
--> src/main.rs:169:19
|
169 | let (P_0, mut Q) = isqrt_rem(D);
| ^ help: convert the identifier to snake case: `q`
warning: variable `P_prev` should have a snake case name
--> src/main.rs:173:13
|
173 | let mut P_prev = P_0;
| ^^^^^^ help: convert the identifier to snake case: `p_prev`
warning: variable `Q_prev` should have a snake case name
--> src/main.rs:174:13
|
174 | let mut Q_prev = 1;
| ^^^^^^ help: convert the identifier to snake case: `q_prev`
warning: variable `P` should have a snake case name
--> src/main.rs:175:13
|
175 | let mut P = P_0;
|
ソースコード
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 より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_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_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")};}//use std::io::Write;// https://judge.yosupo.jp/submission/17650 よりfn gcd(mut a: u64, mut b: u64) -> u64 {if a == 0 || b == 0 {return a + b;}let k = (a | b).trailing_zeros();a >>= a.trailing_zeros();b >>= b.trailing_zeros();while a != b {if a < b {std::mem::swap(&mut a, &mut b);}a -= b;a >>= a.trailing_zeros();}a << k}/*fn mul(a: u64, b: u64, m: u64) -> u64 {let a = a as u128;let b = b as u128;let m = m as u128;((a * b) % m) as u64}*/fn mul(mut a: u64, mut b: u64, m: u64) -> u64 {let mut x = 0;while a > 0 {if a % 2 > 0 {x += b;if x >= m {x -= m;}}a /= 2;b += b;if b >= m {b -= m;}}x}fn powmod(mut a: u64, mut e: u64, m: u64) -> u64 {let mut x = 1;while e > 0 {if e % 2 > 0 {x = mul(x, a, m);}a = mul(a, a, m);e /= 2;}x}fn is_prime(n: u64) -> bool {if n <= 3 {return n == 2 || n == 3;}if n % 2 == 0 {return false;}let mut test = [2, 325, 9375, 28178, 450775, 9780504, 1795265022].iter().filter(|&&a| a <= n - 2);let r = (n - 1).trailing_zeros();let d = (n - 1) >> r;'witness_loop: loop {if let Some(a) = test.next() {let mut x = powmod(a % n, d, n);if x == 1 || x == n - 1 {continue 'witness_loop;}let mut i = r;for i in 0..r {x = mul(x, x, n);if x == n - 1 {continue 'witness_loop;}}return false;} else {return true;}}}/// return (res, rem) such that res^2 + rem = n;fn isqrt_rem(n: u64) -> (u64, u64) {let mut rem = n;let mut res = 0;let mut one = 1;while 4u64.saturating_mul(one) <= n {one *= 4;}while one != 0 {if rem >= res + one {rem -= res + one;res = res + 2 * one;}res /= 2;one /= 4;}(res, rem)}fn squfof(n: u64) -> u64 {let (s, rem) = isqrt_rem(n);if rem == 0 {return s;}let B = (6 * isqrt_rem(2 * s).0) as usize;for k in (1..).step_by(2) {let D = k * n;let (P_0, mut Q) = isqrt_rem(D);if Q == 0 {continue;}let mut P_prev = P_0;let mut Q_prev = 1;let mut P = P_0;let mut r = 0;let mut i = 2;while i < B {let b = (P_0 + P) / Q;P = b * Q - P;let q = Q;Q = Q_prev + b * (P_prev - P);let res_rem = isqrt_rem(Q);r = res_rem.0;if i % 2 == 0 && res_rem.1 == 0 {break;}Q_prev = q;P_prev = P;i += 1;}if i >= B {continue;}let b = (P_0 - P) / r;P = b * r + P;P_prev = P;Q_prev = r;Q = (D - P_prev * P_prev) / Q_prev;i = 0;loop {let b = (P_0 + P) / Q;P_prev = P;P = b * Q - P;let q = Q;Q = Q_prev + b * (P_prev - P);Q_prev = q;i += 1;if P == P_prev {break;}}r = gcd(n, Q_prev);if r != 1 && r != n {return r;}}unreachable!()}fn factor(n: u64) -> Vec<u64> {let mut result = vec![];let mut stack = vec![n];while let Some(n) = stack.pop() {if n == 1 {continue;} else if is_prime(n) {result.push(n);} else {let x = squfof(n);stack.push(x);stack.push(n / x);}}result}// コピペ終わりfn run() {let out = std::io::stdout();let mut out = std::io::BufWriter::new(out.lock());input! {s: usize,ask: [(u64, u64); s],}for (x, y) in ask {let mut f = factor(x + y);f.sort();let mut d = vec![1];let mut i = 0;while i < f.len() {let p = f[i];let mut c = 0;while i < f.len() && f[i] == p {i += 1;c += 1;}let len = d.len();let mut mul = 1;for _ in 1..=c {mul *= p;for i in 0..len {let v = d[i] * mul;d.push(v);}}}let mut ans = 0;for d in d {if d == 1 {continue;}let sum = (x + y) / d;if sum <= 1 {continue;}let a = d - 1;if a == 1 {if x == y {ans += sum - 1;}} else if x > sum && y > sum {let b = (x - sum) / (a - 1);let c = (y - sum) / (a - 1);if a * b + c == x && a * c + b == y {ans += 1;}}}writeln!(out, "{}", ans).ok();}}fn main() {run();}