/* -*- coding: utf-8 -*- * * 2125.cc: No.2125 Inverse Sum - yukicoder */ #include #include #include #include using namespace std; /* constant */ const int MAX_P = 32000; /* typedef */ typedef long long ll; typedef vector vi; typedef pair pii; typedef pair pll; typedef vector vpii; typedef vector vpll; /* global variables */ bool primes[MAX_P + 1]; /* subroutines */ int gen_primes(int maxp, vi &pnums) { fill(primes, primes + maxp + 1, true); primes[0] = primes[1] = false; int p; for (p = 2; p * p <= maxp; p++) if (primes[p]) { pnums.push_back(p); for (int q = p * p; q <= maxp; q += p) primes[q] = false; } for (; p <= maxp; p++) if (primes[p]) pnums.push_back(p); return (int)pnums.size(); } bool prime_decomp(int n, vi &pnums, vpii& pds) { pds.clear(); int pn = pnums.size(); for (int i = 0; i < pn; i++) { int pi = pnums[i]; if (pi * pi > n) { if (n > 1) pds.push_back(pii(n, 1)); return true; } if (n % pi == 0) { int fi = 0; while (n % pi == 0) n /= pi, fi++; pds.push_back(pii(pi, fi)); } } return false; } template T gcd(T m, T n) { // m >= 0, n >= 0 if (m < n) swap(m, n); while (n > 0) { T r = m % n; m = n; n = r; } return m; } void printpds(vpii &pds) { int n = pds.size(); for (int i = 0; i < n; i++) printf("%d^%d%c", pds[i].first, pds[i].second, (i + 1 < n) ? '+' : '\n'); } ll powi(ll a, int b) { ll p = 1; while (b > 0) { if (b & 1) p *= a; a *= a; b >>= 1; } return p; } ll calc(vpii &pds, vi &es) { ll p = 1; for (int i = 0; i < pds.size(); i++) p *= powi(pds[i].first, es[i]); return p; } /* main */ int main() { vi pnums; gen_primes(MAX_P, pnums); int p, q; scanf("%d%d", &p, &q); int g = gcd(p, q); p /= g, q /= g; if (p > q * 2) { puts("0"); return 0; } // 1/n+1/m=p/q -> q(n+m)=pnm -> pn*pm-pn*q-pm*q=0 -> (pn-q)(pm-q)=q^2 vpii pds; prime_decomp(q, pnums, pds); for (auto &pd: pds) pd.second *= 2; //printpds(pds); ll qq = (ll)q * q; int n = pds.size(); vi es(n, 0); vpll ans; for (;;) { ll x = calc(pds, es); ll y = qq / x; if ((x + q) % p == 0 && (y + q) % p == 0) ans.push_back(pll((x + q) / p, (y + q) / p)); int k = 0; for (; k < n; k++) { if (++es[k] > pds[k].second) es[k] = 0; else break; } if (k >= n) break; } sort(ans.begin(), ans.end()); printf("%lu\n", ans.size()); for (auto &nm: ans) printf("%lld %lld\n", nm.first, nm.second); return 0; }