Educational Codeforces Round 142 (Rated for Div. 2)

E. Divisors and Table

\(m=m_1\cdot m_2\)

找 \(m\) 的所有因子，记为数组 \(x\)。

对于 \(x_i\)，找它的最大的小于等于 \(n\) 的因子 \(y\)，那么 \(x_i\) 的贡献为 \(\frac{x_i}{y}\) (当 \(\frac{x_i}{y}>n\) 时，贡献为 \(0\))

先用板子求出 \(m\) 的所有质因子和所有因子。

如果 \(x_i\) 小于 \(n\)，那他的贡献肯定是 \(1\)。

接下来就是如何用 \(m\) 的质因子来求 \(x_i\) 的最大因子。

记 \(f(x)\) 为 \(x\) 的最大的小于等于 \(n\) 的因子。

样例 \(1\) 当我们遍历到 \(3\) 的时候就可以更新所有 \(3\) 的倍数且是 \(m\) 的因子的数。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

// constexpr int M = 998244353;
// constexpr int M = 1000000007;

using i128 = __int128;

i64 POW(i64 a, i64 b, i64 mod) {
  i64 res = 1;
  while (b) {
    if (b & 1) {
      res = (i128)res * a % mod;
    }
    b >>= 1;
    a = (i128)a * a % mod;
  }
  return res;
}

bool is_prime(i64 p) {
  if (p < 2) {
    return 0;
  }
  i64 d = p - 1, r = 0;
  while (!(d & 1)) {
    r++;
    d >>= 1;
  }
  int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
  for (int k = 0; k < 9; k++) {
    if (p == prime[k]) {
      return true;
    }
    i64 x = POW(prime[k], d, p);
    if (x == 1 || x == p - 1) {
      continue;
    }
    for (int i = 0; i < r - 1; i++) {
      x = (i128)x * x % p;
      if (x == p - 1) {
        break;
      }
    }
    if (x != p - 1) {
      return false;
    }
  }
  return true;
}

mt19937
    rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());

i64 pollard_rho(i64 x) {
  i64 s = 0, t = 0;
  i64 c = (i64)rng() % (x - 1) + 1;
  i64 val = 1;
  for (int goal = 1;; goal <<= 1, s = t, val = 1) {
    for (int step = 1; step <= goal; step++) {
      t = ((i128)t * t + c) % x;
      val = (i128)val * abs(t - s) % x;
      if (step % 127 == 0) {
        i64 g = gcd(val, x);
        if (g > 1) {
          return g;
        }
      }
    }
    i64 g = __gcd(val, x);
    if (g > 1) {
      return g;
    }
  }
}

unordered_map<i64, int> primes;

void get(i64 x) {
  if (x < 2) {
    return;
  }
  if (is_prime(x)) {
    primes[x]++;
    return;
  }
  i64 mx = pollard_rho(x);
  get(x / mx);
  get(mx);
}

void getprimes(i64 x) {
  primes.clear();
  get(x);
}

vector<i64> fac;

void getfac(i64 x) {
  fac.clear();
  getprimes(x);
  vector<pair<i64, int>> tmp(primes.begin(), primes.end());
  int SIZE = tmp.size();
  function<void(int, i64)> dfs = [&](int id, i64 x) {
    if (id == SIZE) {
      fac.push_back(x);
      return;
    }
    i64 p = 1;
    for (int i = 0; i <= tmp[id].second; i++) {
      if (i != 0) {
        p *= tmp[id].first;
      }
      dfs(id + 1, x * p);
    }
  };
  dfs(0, 1);
}

void solve() {
  int n, m1, m2;
  cin >> n >> m1 >> m2;
  i64 m = 1LL * m1 * m2;
  getfac(m);
  unordered_map<i64, int> mp(1024);
  mp.max_load_factor(0.25);
  for (auto x : fac) {
    if (x <= n) {
      mp[x] = x;
    }
    for (auto [y, useless] : primes) {
      i64 t = x * y;
      if (t > m) {
        continue;
      }
      if (m % t == 0) {
        mp[t] = max(mp[t], mp[x]);
      }
    }
  }
  int cnt = 0;
  int ans = 0;
  for (auto [x, y] : mp) {
    if (x / y <= n) {
      cnt++;
      ans ^= x / y;
    }
  }
  cout << cnt << ' ' << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}