面白かった

問題へのリンク

問題概要

正の整数 $p, q$ が与えられる。

$p$ の約数であって、 $q$ の倍数ではないような整数の最大値を求めよ。

(というデータセットが $T$ 個与えられる)

制約

$1 \le T \le 50$
$1 \le p \le 10^{18}$
$2 \le q \le 10^{9}$

考えたこと

$p$ の約数をすべて列挙したのでは間に合わない。とりあえず $p$ 自身が $q$ で割り切れないならば、 $p$ が答えになることはわかる。

$p$ が $q$ で割り切れるとき、次のことがわかる。 $q$ を素因数分解して

$q = q_{1}^{e_{1}} q_{2}^{e_{2}} \times q_{k}^{e_{k}}$

としたとき、 $p$ の $q_{1}, \dots, q_{k}$ に対する指数がそれぞれ $e_{1}, \dots, e_{k}$ 以上となる。

よって、 $p$ の約数であって $q$ の倍数でないような、なるべく大きい整数を作るためには、

$p$ の $q_{1}$ に対する指数を $e_{1}-1$ まで下げたもの
$p$ の $q_{2}$ に対する指数を $e_{2}-1$ まで下げたもの
...
$p$ の $q_{k}$ に対する指数を $e_{k}-1$ まで下げたもの

を比較して、そのうち最大のものを求めれば OK。計算量は $O(\sqrt{q} + \log p \log q)$ 。

#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

long long solve(long long P, long long Q) {
    if (P % Q != 0) return P;
    auto pf = prime_factorize(Q);
    long long res = 0;
    for (auto it : pf) {
        long long P2 = P;
        long long p = it.first, e = it.second;
        while (P2 % p == 0) P2 /= p;
        for (long long j = 0; j < e-1; ++j) P2 *= p;
        chmax(res, P2);
    }
    return res;
}

int main() {
    int T; cin >> T;
    while (T--) {
        long long p, q; cin >> p >> q;
        cout << solve(p, q) << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #680 (Div. 1) A. Division (R1500)

問題概要

制約

考えたこと