結果

問題 No.1006 Share an Integer
コンテスト
ユーザー mikianaaa
提出日時 2020-08-29 16:09:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 494 ms / 2,000 ms
コード長 1,688 bytes
コンパイル時間 1,948 ms
コンパイル使用メモリ 176,884 KB
実行使用メモリ 50,224 KB
最終ジャッジ日時 2024-11-14 14:11:08
合計ジャッジ時間 7,802 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define LL long long
#define ld long double
#define INF 1000000000000000000
typedef pair<LL, LL> PLL;

vector<LL> SPF(LL n) {
    vector<LL> spf(n + 1);
    for (int i = 0; i <= n; i++)
        spf[i] = i;

    for (LL i = 2; i * i <= n; i++) {
        if (spf[i] == i) {
            for (LL j = i * i; j <= n; j += i) {
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }
    return spf;
}

LL primes(LL x, vector<LL> &spf, vector<LL> &dp) {
    if (dp[x] != -1) {
        return dp[x];
    }
    LL o = x;
    vector<LL> a;
    while (x != 1) {
        a.push_back(spf[x]);
        x /= spf[x];
    }
    LL d = 1;
    int n = a.size();
    for (int i = 0, j = 0; i < n; i = j) {
        while (j < n and a[i] == a[j])
            j++;
        d *= (j - i + 1);
    }
    return dp[o] = d;
}

constexpr LL MAX = 3000000;

int main() {

    LL X;
    cin >> X;

    auto spf = SPF(MAX);

    LL maxV = 1e18;
    vector<LL> dp(MAX, -1);
    for (LL a = 1; a < X; a++) {
        LL b = X - a;
        LL val = abs((b - a) + (primes(a, spf, dp) - primes(b, spf, dp)));
        if (val < maxV) {
            maxV = val;
        }
    }
    vector<PLL> ret;
    for (LL a = 1; a < X; a++) {
        LL b = X - a;
        LL val = abs((b - a) + (primes(a, spf, dp) - primes(b, spf, dp)));
        if (val == maxV) {
            ret.push_back(make_pair(a, b));
        }
    }
    sort(all(ret));
    for (auto x : ret)
        cout << x.first << " " << x.second << endl;
}
0