結果

問題 No.376 立方体のN等分 (2)
コンテスト
ユーザー はまやんはまやん
提出日時 2018-09-04 14:51:50
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,010 bytes
コンパイル時間 2,122 ms
コンパイル使用メモリ 183,600 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-13 10:27:11
合計ジャッジ時間 3,344 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
#define MAXL (50000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXL];
int P[50000], Pt = 0;
void init() {
    register int i, j, k;
    SET(1);
    int n = 46340;
    for (i = 2; i <= n; i++) {
        if (!GET(i)) {
            for (k = n / i, j = i * k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
long long mul(unsigned long long a, unsigned long long b, unsigned long long mod) {
    long long ret = 0;
    for (a %= mod, b %= mod; b != 0; b >>= 1, a <<= 1, a = a >= mod ? a - mod : a) {
        if (b & 1) {
            ret += a;
            if (ret >= mod) ret -= mod;
        }
    }
    return ret;
}
void exgcd(long long x, long long y, long long &g, long long &a, long long &b) {
    if (y == 0)
        g = x, a = 1, b = 0;
    else
        exgcd(y, x%y, g, b, a), b -= (x / y) * a;
}
long long llgcd(long long x, long long y) {
    if (x < 0)    x = -x;
    if (y < 0)    y = -y;
    if (!x || !y)    return x + y;
    long long t;
    while (x%y)
        t = x, x = y, y = t % y;
    return y;
}
long long inverse(long long x, long long p) {
    long long g, b, r;
    exgcd(x, p, g, r, b);
    if (g < 0)  r = -r;
    return (r%p + p) % p;
}
long long mpow(long long x, long long y, long long mod) { // mod < 2^32 
    long long ret = 1;
    while (y) {
        if (y & 1)
            ret = (ret * x) % mod;
        y >>= 1, x = (x * x) % mod;
    }
    return ret % mod;
}
long long mpow2(long long x, long long y, long long mod) {
    long long ret = 1;
    while (y) {
        if (y & 1)
            ret = mul(ret, x, mod);
        y >>= 1, x = mul(x, x, mod);
    }
    return ret % mod;
}
int isPrime(long long p) { // implements by miller-babin
    if (p < 2 || !(p & 1))  return 0;
    if (p == 2)             return 1;
    long long q = p - 1, a, t;
    int k = 0, b = 0;
    while (!(q & 1))    q >>= 1, k++;
    for (int it = 0; it < 2; it++) {
        a = rand() % (p - 4) + 2;
        t = mpow2(a, q, p);
        b = (t == 1) || (t == p - 1);
        for (int i = 1; i < k && !b; i++) {
            t = mul(t, t, p);
            if (t == p - 1)
                b = 1;
        }
        if (b == 0)
            return 0;
    }
    return 1;
}
long long pollard_rho(long long n, long long c) {
    long long x = 2, y = 2, i = 1, k = 2, d;
    while (true) {
        x = (mul(x, x, n) + c);
        if (x >= n) x -= n;
        d = llgcd(x - y, n);
        if (d > 1) return d;
        if (++i == k) y = x, k <<= 1;
    }
    return n;
}
void factorize(int n, vector<long long> &f) {
    for (int i = 0; i < Pt && P[i] * P[i] <= n; i++) {
        if (n%P[i] == 0) {
            while (n%P[i] == 0)
                f.push_back(P[i]), n /= P[i];
        }
    }
    if (n != 1) f.push_back(n);
}
void llfactorize(long long n, vector<long long> &f) {
    if (n == 1)
        return;
    if (n < 1e+9) {
        factorize(n, f);
        return;
    }
    if (isPrime(n)) {
        f.push_back(n);
        return;
    }
    long long d = n;
    for (int i = 2; d == n; i++)
        d = pollard_rho(n, i);
    llfactorize(d, f);
    llfactorize(n / d, f);
}
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/





//---------------------------------------------------------------------------------------------------
vector<ll> enumdiv(ll x) {
    if (x < 1000000000) {
        vector<ll> S;
        for (ll i = 1; i*i <= x; i++) if (x%i == 0) { S.push_back(i); if (i*i != x) S.push_back(x / i); }
        sort(S.begin(), S.end());
        return S;
    }

    vector<ll> v, res;
    llfactorize(x, v);

    map<ll, int> cnt;
    fore(i, v) cnt[i]++;

    res.push_back(1);
    vector<ll> buf; buf.push_back(1);
    fore(pa, cnt) {
        ll p = pa.first;
        int c = pa.second;

        vector<ll> nxt;
        fore(y, buf) {
            ll yy = y;
            rep(i, 1, c + 1) {
                yy *= p;
                res.push_back(yy);
                nxt.push_back(yy);
            }
        }
        fore(y, nxt) buf.push_back(y);
    }

    sort(all(res));
    return res;
}





ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    ll tmin = infl, tmax = -infl;
    
    auto dv = enumdiv(N);

    /*fore(a, dv) {
        ll rest = N / a;
        auto dv2 = enumdiv(rest);
        fore(b, dv2) {
            ll c = rest / b;

            chmin(tmin, a + b + c - 3);
            chmax(tmax, a + b + c - 3);
        }
    }*/

    int n = dv.size();
    rep(i, 0, n) rep(j, 0, n) {
        ll a = dv[i], b = dv[j];
        if (N % a == 0) if ((N / a) % b == 0) {
            ll c = N / a / b;
            chmin(tmin, a + b + c - 3);
            chmax(tmax, a + b + c - 3);
        }
    }

    printf("%lld %lld\n", tmin, tmax);
}
0