結果

問題 No.2929 Miracle Branch
コンテスト
ユーザー 👑 loop0919
提出日時 2024-09-13 17:12:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,491 bytes
コンパイル時間 1,710 ms
コンパイル使用メモリ 143,008 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-09-13 17:12:14
合計ジャッジ時間 10,335 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2 RE * 1
other WA * 15 RE * 10 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <random>

using namespace std;
using ll = long long;

// Pollard's Rho 法による素因数分解
ll gcd(ll a, ll b) {
    while (b) {
        ll t = a % b;
        a = b;
        b = t;
    }
    return a;
}

ll pollards_rho(ll n) {
    if (n % 2 == 0) return 2;
    random_device rd;
    mt19937 mt(rd());
    uniform_int_distribution<ll> dist(1, n - 1);
    ll x = dist(mt);
    ll y = x;
    ll c = dist(mt);
    ll d = 1;
    while (d == 1) {
        x = ( (__int128_t(x) * x) % n + c ) % n;
        y = ( (__int128_t(y) * y) % n + c ) % n;
        y = ( (__int128_t(y) * y) % n + c ) % n;
        d = gcd(abs(x - y), n);
        if (d == n) return pollards_rho(n);
    }
    return d;
}

bool is_prime(ll n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n%2 == 0 || n%3 == 0) return false;
    ll i = 5;
    while (i*i <= n) {
        if (n%i == 0 || n%(i+2) == 0) return false;
        i += 6;
    }
    return true;
}

void factorize(ll n, map<ll, int> &factors) {
    if (n == 1) return;
    if (n <= 1e6) {
        // エラトステネスの篩による素数判定
        for (ll i = 2; i * i <= n; ++i) {
            int cnt = 0;
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            if (cnt > 0) factors[i] += cnt;
        }
        if (n > 1) factors[n]++;
        return;
    }
    if (is_prime(n)) {
        factors[n]++;
        return;
    }
    ll d = pollards_rho(n);
    factorize(d, factors);
    factorize(n / d, factors);
}

int main() {
    ll X;
    cin >> X;

    const int MAX_N = 200000;

    if (X == 1) {
        // 特別な場合
        cout << -1 << endl;
        return 0;
    }

    map<ll, int> factors;
    factorize(X, factors);

    // 素因数を指数の降順で並べる
    vector<pair<ll, int>> pf(factors.begin(), factors.end());
    sort(pf.begin(), pf.end(), [](pair<ll, int> &a, pair<ll, int> &b) {
        return a.second > b.second;
    });

    // 茶色の頂点数を決定（素因数の個数）
    int brown_nodes = 0;
    for (auto &p : pf) {
        brown_nodes += p.second;
    }

    if (brown_nodes + brown_nodes - 1 > MAX_N) {
        cout << -1 << endl;
        return 0;
    }

    int n = brown_nodes + brown_nodes - 1; // 茶色の頂点 + 緑色の頂点

    cout << n << endl;

    // 茶色の頂点を線状に配置
    int node_id = 1;
    vector<int> brown_ids;
    for (int i = 0; i < brown_nodes; ++i) {
        brown_ids.push_back(node_id++);
    }

    // 辺の出力
    for (int i = 0; i < (int)brown_ids.size() - 1; ++i) {
        cout << brown_ids[i] << " " << brown_ids[i+1] << endl;
    }

    // 緑色の頂点を茶色の頂点に接続
    vector<char> colors(n + 1);
    for (int i = 0; i < (int)pf.size(); ++i) {
        for (int j = 0; j < pf[i].second; ++j) {
            int brown_node = brown_ids.back();
            brown_ids.pop_back();
            colors[brown_node] = 'b';
            for (int k = 0; k < pf[i].first - 1; ++k) {
                int green_node = node_id++;
                cout << brown_node << " " << green_node << endl;
                colors[green_node] = 'g';
            }
        }
    }

    // 色の出力
    for (int i = 1; i <= n; ++i) {
        if (i != 1) cout << " ";
        if (colors[i] == 'b') cout << 'b';
        else cout << 'g';
    }
    cout << endl;

    return 0;
}
0