結果
問題 | No.1200 お菓子配り-3 |
ユーザー |
👑 |
提出日時 | 2020-08-29 03:36:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 658 ms / 4,000 ms |
コード長 | 4,186 bytes |
コンパイル時間 | 1,059 ms |
コンパイル使用メモリ | 107,660 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-20 22:52:09 |
合計ジャッジ時間 | 7,691 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 3 ms
6,816 KB |
testcase_04 | AC | 3 ms
6,816 KB |
testcase_05 | AC | 3 ms
6,820 KB |
testcase_06 | AC | 3 ms
6,820 KB |
testcase_07 | AC | 7 ms
6,820 KB |
testcase_08 | AC | 7 ms
6,816 KB |
testcase_09 | AC | 8 ms
6,820 KB |
testcase_10 | AC | 7 ms
6,820 KB |
testcase_11 | AC | 8 ms
6,820 KB |
testcase_12 | AC | 58 ms
6,820 KB |
testcase_13 | AC | 57 ms
6,816 KB |
testcase_14 | AC | 58 ms
6,816 KB |
testcase_15 | AC | 56 ms
6,820 KB |
testcase_16 | AC | 56 ms
6,816 KB |
testcase_17 | AC | 205 ms
6,816 KB |
testcase_18 | AC | 295 ms
6,820 KB |
testcase_19 | AC | 64 ms
6,816 KB |
testcase_20 | AC | 537 ms
6,816 KB |
testcase_21 | AC | 569 ms
6,820 KB |
testcase_22 | AC | 658 ms
6,816 KB |
testcase_23 | AC | 561 ms
6,816 KB |
testcase_24 | AC | 536 ms
6,816 KB |
testcase_25 | AC | 549 ms
6,816 KB |
testcase_26 | AC | 555 ms
6,816 KB |
testcase_27 | AC | 2 ms
6,820 KB |
testcase_28 | AC | 407 ms
6,816 KB |
testcase_29 | AC | 173 ms
6,820 KB |
testcase_30 | AC | 169 ms
6,816 KB |
testcase_31 | AC | 2 ms
6,820 KB |
testcase_32 | AC | 2 ms
6,820 KB |
ソースコード
#include <cassert> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using Int = long long; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } template<class T> vector<T> merge(const vector<T> &a, const vector<T> &b) { vector<T> c(a.size() + b.size()); std::merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); return c; } template<class T> T power(T a, Int e, T m) { T b = 1; for (; e; e >>= 1) { if (e & 1) b = (b * a) % m; a = (a * a) % m; } return b; } Int gcd(Int a, Int b) { if (a < 0) a = -a; if (b < 0) b = -b; if (a == 0) return b; if (b == 0) return a; const int s = __builtin_ctzll(a | b); a >>= __builtin_ctzll(a); do { b >>= __builtin_ctzll(b); if (a > b) std::swap(a, b); b -= a; } while (b); return a << s; } // Checks if n is a prime using Miller-Rabin test bool isPrime(Int n) { if (n <= 1 || n % 2 == 0) return (n == 2); const int s = __builtin_ctzll(n - 1); const Int d = (n - 1) >> s; // http://miller-rabin.appspot.com/ for (const Int base : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) { __int128_t a = base % n; if (a == 0) continue; a = power<__int128_t>(a, d, n); if (a == 1 || a == n - 1) continue; bool ok = false; for (int i = 0; i < s - 1; ++i) { a = (a * a) % n; if (a == n - 1) { ok = true; break; } } if (!ok) return false; } return true; } // Factorize n using Pollard's rho algorithm vector<Int> factorize(Int n) { if (n <= 1) return {}; if (isPrime(n)) return {n}; if (n % 2 == 0) return merge({2}, factorize(n / 2)); for (Int c = 1; ; ++c) { Int x = 2, y = 2, d; do { x = (static_cast<__int128_t>(x) * x + c) % n; y = (static_cast<__int128_t>(y) * y + c) % n; y = (static_cast<__int128_t>(y) * y + c) % n; d = gcd(x - y, n); } while (d == 1); if (d < n) return merge(factorize(d), factorize(n / d)); } } int psLen; vector<Int> ps, ds; void dfs(int pos, Int d, bool skipped) { if (pos == psLen) { ds.push_back(d); } else { dfs(pos + 1, d, true); if (!skipped || ps[pos - 1] < ps[pos]) { dfs(pos + 1, d * ps[pos], false); } } } vector<Int> getDivisors(Int n) { ps = factorize(n); psLen = ps.size(); ds.clear(); dfs(0, 1, false); cerr<<"getDivisors "<<n<<" = ";pv(ds.begin(),ds.end()); return ds; } int main() { int numCases; for (; ~scanf("%d", &numCases); ) { for (int caseId = 0; caseId < numCases; ++caseId) { Int X, Y; scanf("%lld%lld", &X, &Y); if (X > Y) { swap(X, Y); } Int ans = 0; if (X == Y) { // B = C auto check0 = [&](Int d) { if (d > 1) { ++ans; } }; const auto ds = getDivisors(X); for (const Int d : ds) { check0(d); } // A = 1, B != C ans += (X - 1) / 2 * 2; } else { auto check = [&](Int d) { const Int a = d + 1; const Int denom = a * a - 1; const Int numerB = a * X - Y; const Int numerC = a * Y - X; if (numerB > 0 && numerC > 0 && numerB % denom == 0 && numerC % denom == 0) { ++ans; } }; const auto ds = getDivisors(Y - X); for (const Int d : ds) { check(d); } } printf("%lld\n", ans); } } return 0; }