結果

問題 No.1200 お菓子配り-3
ユーザー 👑 hos.lyric
提出日時 2020-08-29 03:36:35
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0