結果

問題 No.1006 Share an Integer
ユーザー mikianaaamikianaaa
提出日時 2020-08-29 16:09:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 492 ms / 2,000 ms
コード長 1,688 bytes
コンパイル時間 2,794 ms
コンパイル使用メモリ 173,712 KB
実行使用メモリ 50,304 KB
最終ジャッジ日時 2024-04-26 22:27:45
合計ジャッジ時間 8,063 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 69 ms
50,176 KB
testcase_01 AC 71 ms
50,048 KB
testcase_02 AC 76 ms
50,048 KB
testcase_03 AC 74 ms
50,048 KB
testcase_04 AC 74 ms
50,176 KB
testcase_05 AC 73 ms
50,048 KB
testcase_06 AC 69 ms
50,176 KB
testcase_07 AC 70 ms
50,048 KB
testcase_08 AC 71 ms
50,176 KB
testcase_09 AC 71 ms
50,176 KB
testcase_10 AC 70 ms
50,304 KB
testcase_11 AC 290 ms
50,048 KB
testcase_12 AC 464 ms
50,048 KB
testcase_13 AC 492 ms
50,048 KB
testcase_14 AC 491 ms
50,048 KB
testcase_15 AC 427 ms
50,048 KB
testcase_16 AC 231 ms
50,048 KB
testcase_17 AC 292 ms
50,304 KB
testcase_18 AC 430 ms
50,048 KB
testcase_19 AC 412 ms
50,176 KB
testcase_20 AC 436 ms
50,048 KB
testcase_21 AC 490 ms
50,304 KB
権限があれば一括ダウンロードができます

ソースコード

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