結果

問題 No.1383 Numbers of Product
コンテスト
ユーザー vjudge1
提出日時 2026-09-21 22:57:50
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 199 ms / 2,000 ms
+ 225µs
コード長 2,582 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 545 ms
コンパイル使用メモリ 104,136 KB
実行使用メモリ 29,540 KB
最終ジャッジ日時 2026-09-21 22:57:58
合計ジャッジ時間 8,256 ms
ジャッジサーバーID
（参考情報） 		judge5_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool is_P1(long long X, long long K) {
    long long L = 1, R = 1e9;
    if (X < R) R = X;
    while (L <= R) {
        long long mid = L + (R - L) / 2;
        __int128_t val = (__int128_t)mid * (mid + K);
        if (val == X) return true;
        if (val < X) L = mid + 1;
        else R = mid - 1;
    }
    return false;
}

long long get_max_A(long long N, long long K) {
    long long L = 1, R = 1e9;
    long long res = 0;
    while (L <= R) {
        long long mid = L + (R - L) / 2;
        if ((__int128_t)mid * (mid + K) <= N) {
            res = mid;
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long N, K, M;
    if (!(cin >> N >> K >> M)) return 0;

    vector<long long> S_gt1;
    
    for (int B = 2; ; ++B) {
        __int128_t prod = 1;
        bool ok = true;
        for (int i = 0; i <= B; ++i) {
            prod *= (1 + i * (__int128_t)K);
            if (prod > N) {
                ok = false;
                break;
            }
        }
        if (!ok) break; 

        for (long long A = 1; ; ++A) {
            __int128_t current_prod = A;
            bool A_ok = true;
            for (int i = 1; i <= B; ++i) {
                current_prod *= (A + i * (__int128_t)K);
                if (current_prod > N) {
                    A_ok = false;
                    break;
                }
            }
            if (!A_ok) break;
            S_gt1.push_back((long long)current_prod);
        }
    }

    sort(S_gt1.begin(), S_gt1.end());
    vector<pair<long long, int>> V;
    for (size_t i = 0; i < S_gt1.size(); ) {
        size_t j = i;
        while (j < S_gt1.size() && S_gt1[j] == S_gt1[i]) j++;
        V.push_back({S_gt1[i], (int)(j - i)});
        i = j;
    }

    long long ans = 0;
    long long MAX_A = get_max_A(N, K);

    if (M == 1) {
        ans = MAX_A;
        for (auto p : V) {
            long long X = p.first;
            int count = p.second;
            bool has_1 = is_P1(X, K);
            
            if (has_1) ans--;           
            else if (count == 1) ans++; 
        }
    } else {
        for (auto p : V) {
            long long X = p.first;
            int count = p.second;
            bool has_1 = is_P1(X, K);
            int total_freq = count + (has_1 ? 1 : 0);
            
            if (total_freq == M) ans++; 
        }
    }

    cout << ans << "\n";

    return 0;
}
0