2021牛客寒假算法基础集训营4 J. 邬澄瑶的公约数(数学)

Description

一句话题意：给定 $n$ 个数字 $x_i$ ( $1 \leq i \leq n$ ), $n$ 个数字 $p_i$ ( $1 \leq i \leq n$ )
求 $gcd(x_{1}^{p_1},\dots,x_{n}^{p_n})$

Solution

我们先考虑下子问题：求 $gcd(x_1,\dots,x_n)$ , 无非就是质因数分解，然后找到大家都有的因子, 以及这个因子出现的最小次数。

举个例子： $gcd(24, 32, 36) = gcd(2^3\cdot3, 2^4, 2^2\cdot3^2)$ , 共同出现的质因子是 $2$ , 分别出现了 $3, 4, 2$ 次，那么最小次数就是 $2$ , 因此 $gcd(24, 32, 36) = 2^2 = 4$

回到本题目来，该问题中多了 $p_i$ , 我们知道 $(a^b)^c = a^{b\cdot c}$ , 那么同样地只需要在原来的子问题中找到出现了 $n$ 次的质因子的最小次数，将最小次数乘以对应的 $p_i$ 即可。

时间复杂度 $O(n\sqrt{max(x_i)})$ 。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, M = 1e7 + 10, mod = 1e9 + 7;
ll qpow(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b & 1) {
      res = res * a % mod;
    }
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
void solve() {
  int n; cin >> n;
  vector<int> x(n), p(n);
  unordered_map<int, int> mp, cot;
  for (int i = 0; i < n; i++) {
    cin >> x[i];
  }  
  for (int i = 0; i < n; i++) {
    cin >> p[i];
  }
  for (int i = 0; i < n; i++) {
    int pre = x[i];
    for (int j = 2; 1LL * j * j <= pre; j++) {
      if (pre % j == 0) {
        mp[j]++;
        int cnt = 0;
        while (pre % j == 0) {
          pre /= j, cnt++;
        }
        cnt *= p[i];
        if (!cot.count(j)) {
          cot[j] = cnt;
        } else {
          cot[j] = min(cot[j], cnt);
        }
      }
    }
    if (pre > 1) {
      mp[pre]++;
      if (!cot.count(pre)) {
        cot[pre] = p[i];
      } else {
        cot[pre] = min(cot[pre], p[i]);
      }
    }
  }
  vector<int> v;
  for (auto &u : mp) {
    if (u.second == n) {
      v.emplace_back(u.first);
    }
  }
  ll ans = 1;
  for (auto &u : v) {
    ans = ans * qpow(u, cot[u]) % mod;
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int T = 1; //cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}