// ---------- begin enumerate prime ---------- fn enumerate_prime(n: usize, mut f: F) where F: FnMut(usize), { assert!(1 <= n && n <= 5 * 10usize.pow(8)); let batch = (n as f64).sqrt().ceil() as usize; let mut is_prime = vec![true; batch + 1]; for i in (2..).take_while(|p| p * p <= batch) { if is_prime[i] { let mut j = i * i; while let Some(p) = is_prime.get_mut(j) { *p = false; j += i; } } } let mut prime = vec![]; for (i, p) in is_prime.iter().enumerate().skip(2) { if *p && i <= n { f(i); prime.push(i); } } let mut l = batch + 1; while l <= n { let r = std::cmp::min(l + batch, n + 1); is_prime.clear(); is_prime.resize(r - l, true); for &p in prime.iter() { let mut j = (l + p - 1) / p * p - l; while let Some(is_prime) = is_prime.get_mut(j) { *is_prime = false; j += p; } } for (i, _) in is_prime.iter().enumerate().filter(|p| *p.1) { f(i + l); } l += batch; } } // ---------- end enumerate prime ---------- // ---------- begin Exact Division ---------- // reference: https://min-25.hatenablog.com/entry/2017/08/20/171214 pub struct ExactDivision { a: u64, b: u64, shift: u32, } impl ExactDivision { pub fn new(d: u64) -> Self { assert!(d > 0); let shift = d.trailing_zeros(); let d = d >> shift; let mut m = d; for _ in 0..5 { m *= 2 - d * m; } Self { a: !0 / d, b: m, shift: shift, } } pub fn division(&self, val: u64) -> Option { if val & ((1 << self.shift) - 1) != 0 { return None; } let res = (val >> self.shift) * self.b; if res <= self.a { Some(res) } else { None } } } // ---------- end Exact Division ---------- // ---------- begin input macro ---------- // reference: 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::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- use std::io::Write; fn run() { input! { t: usize, ask: [(u64, u64); t], } let m = 10f64.powi(9).sqrt().ceil() as usize; let mut exact = vec![]; enumerate_prime(m, |p| exact.push((p as u64, ExactDivision::new(p as u64)))); let divisor = |mut n: u64| -> Vec { let mut d = vec![1]; for &(p, ref e) in exact.iter() { if p * p > n { break; } let mut c = 0; while let Some(v) = e.division(n) { n = v; c += 1; } let len = d.len(); let mut m = 1; for _ in 1..=c { m *= p; for i in 0..len { let v = d[i] * m; d.push(v); } } } if n > 1 { for i in 0..d.len() { let v = d[i] * n; d.push(v); } } d }; let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); for (x, y) in ask { let mut ans = 0; for d in divisor(x + y) { 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(); }