結果

問題 No.1383 Numbers of Product
ユーザー sten_san
提出日時 2021-02-09 01:32:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,979 bytes
コンパイル時間 2,361 ms
コンパイル使用メモリ 200,484 KB
最終ジャッジ日時 2025-01-18 16:33:45
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11 WA * 10 TLE * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct uns_t {} uns;
template <typename Element, typename Head, typename ...Args>
auto vec(Element init, Head arg, Args ...args) {
    if constexpr (sizeof...(Args) == 0) return std::vector(arg, init);
    else return std::vector(arg, vec(init, args...));
}
template <typename Element, typename Head, typename ...Args>
auto vec(uns_t, Head arg, Args ...args) {
    return vec(Element(), arg, args...);
}

int main() {
    using int128_t = __int128;

    int64_t n, k, m; cin >> n >> k >> m;

    auto pow = [&](auto a, auto b) {
        int128_t ans = 1;
        while (b--) {
            ans *= a;
        }
        return ans;
    };

    auto prod = [&](auto a, auto b) {
        int128_t ans = a;
        for (int i = 1; i <= b; ++i) {
            ans *= a + i * k;
        }
        return ans;
    };

    auto sqrt = [&](auto x) {
        auto left = 0, right = x;
        while (1 < right - left) {
            auto mid = left + (right - left) / 2;
            if (mid * mid <= x) {
                left = mid;
            }
            else {
                right = mid;
            }
        }
        return left;
    };

    auto included = [&](auto x) {
        auto a = __int128(k);
        auto square = a * a + 4 * x;
        auto root = sqrt(square);
        if (root * root != square || (root - a) % 2) return false;
        return true;
    };

    map<int64_t, int> count;
    for (int b = 2; b < 20; ++b) {
        for (int a = 1; prod(a, b) <= n; ++a) {
            ++count[prod(a, b)];
        }
    }

    if (m == 1) {
        int64_t ans = 0;
        for (auto [a, b] : count) {
            ans -= included(a);
        }
        ans += (sqrt(int128_t(k) * k + 4 * n) - k) / 2;

        cout << ans << endl;
        return 0;
    }

    for (auto &[a, b] : count) {
        b += included(a);
    }

    int ans = 0;
    for (auto [a, b] : count) {
        ans += b == m;
    }

    cout << ans << endl;
}
0