QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#419629#6566. Power of DivisorsohiostatescarletCompile Error//C++143.3kb2024-05-24 04:57:192024-05-24 04:57:19

Judging History

你现在查看的是最新测评结果

  • [2024-05-24 04:57:19]
  • 评测
  • [2024-05-24 04:57:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "templates/debug.h"
#else
#define dbg(x...)
#endif

// Always assume a problem requires no fancy algorithms, unless it's obvious.
// Visualize small example cases.
// Think about simpler variations.
// Notice interesting properties.
// Think: If you just had x, you could solve the problem. Can you get x?
using ll = long long;
namespace PollardRho {
  mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  const int P = 1e6 + 9;
  ll seq[P];
  int primes[P], spf[P];
  inline ll add_mod(ll x, ll y, ll m) {
    return (x += y) < m ? x : x - m;
  }
  inline ll mul_mod(ll x, ll y, ll m) {
    ll res = __int128(x) * y % m;
    return res;
  }
  inline ll pow_mod(ll x, ll n, ll m) {
    ll res = 1 % m;
    for (; n; n >>= 1) {
      if (n & 1) res = mul_mod(res, x, m);
      x = mul_mod(x, x, m);
    }
    return res;
  }
  inline bool miller_rabin(ll n) {
    if (n <= 2 || (n & 1 ^ 1)) return (n == 2);
    if (n < P) return spf[n] == n;
    ll c, d, s = 0, r = n - 1;
    for (; !(r & 1); r >>= 1, s++) {}
    for (int i = 0; primes[i] < n && primes[i] < 32; i++) {
      c = pow_mod(primes[i], r, n);
      for (int j = 0; j < s; j++) {
        d = mul_mod(c, c, n);
        if (d == 1 && c != 1 && c != (n - 1)) return false;
        c = d;
      }
      if (c != 1) return false;
    }
    return true;
  }
  void init() {
    int cnt = 0;
    for (int i = 2; i < P; i++) {
      if (!spf[i]) primes[cnt++] = spf[i] = i;
      for (int j = 0, k; (k = i * primes[j]) < P; j++) {
        spf[k] = primes[j];
        if (spf[i] == spf[k]) break;
      }
    }
  }
  // returns O(n^(1/4))
  ll pollard_rho(ll n) {
    while (1) {
      ll x = rnd() % n, y = x, c = rnd() % n, u = 1, v, t = 0;
      ll *px = seq, *py = seq;
      while (1) {
        *py++ = y = add_mod(mul_mod(y, y, n), c, n);
        *py++ = y = add_mod(mul_mod(y, y, n), c, n);
        if ((x = *px++) == y) break;
        v = u;
        u = mul_mod(u, abs(y - x), n);
        if (!u) return __gcd(v, n);
        if (++t == 32) {
          t = 0;
          if ((u = __gcd(u, n)) > 1 && u < n) return u;
        }
      }
      if (t && (u = __gcd(u, n)) > 1 && u < n) return u;
    }
  }
  vector<ll> factorize(ll n) {
    if (n == 1) return vector <ll>();
    if (miller_rabin(n)) return vector<ll> {n};
    vector <ll> v, w;
    while (n > 1 && n < P) {
      v.push_back(spf[n]);
      n /= spf[n];
    }
    if (n >= P) {
      ll x = pollard_rho(n);
      v = factorize(x);
      w = factorize(n / x);
      v.insert(v.end(), w.begin(), w.end());
    }
    return v;
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int64_t x; cin >> x;
  PollardRho::init();
  map<int, int> cnt;
  for (auto i : PollardRho::factorize(x)) {
    cnt[i]++;
  }
  int64_t g = 0;
  for (auto [a, b] : cnt) {
    g = gcd(g, b);
  }
  vector<int> p;
  for (int i = 1; i <= g; i++) {
    if (g % i == 0) p.push_back(i);
  }
  for (auto power : p) {
    int factors = 1;
    int64_t ans = 1;
    for (auto [a, b] : cnt) {
      b /= power;
      factors *= b + 1;
      while (b--) ans *= a;
    }
    if (factors == power) {
      cout << ans << '\n';
      return 0;
    }
  }
  cout << "-1\n";
}

详细

answer.code: In function ‘int main()’:
answer.code:109:13: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  109 |   for (auto [a, b] : cnt) {
      |             ^
answer.code:110:9: error: ‘gcd’ was not declared in this scope
  110 |     g = gcd(g, b);
      |         ^~~
answer.code:119:15: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  119 |     for (auto [a, b] : cnt) {
      |               ^