結果

問題 No.1383 Numbers of Product
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:51:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,657 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 54,440 KB
最終ジャッジ日時 2025-06-12 16:52:48
合計ジャッジ時間 4,400 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 TLE * 1 -- * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def compute_x(A, B, K):
    x = 1
    for i in range(B + 1):
        term = A + i * K
        x *= term
        if x > 1e18 * 2:  # 预留空间避免溢出
            return x
    return x

def count_x(B, K, N):
    x_a1 = 1
    for i in range(B + 1):
        term = 1 + i * K
        x_a1 *= term
        if x_a1 > N:
            return 0
    if x_a1 > N:
        return 0

    low = 1
    high = 1
    while True:
        x_high = compute_x(high, B, K)
        if x_high > N:
            break
        else:
            high *= 2
            if high > 1e18:
                break

    a_max = 0
    while low <= high:
        mid = (low + high) // 2
        x_mid = compute_x(mid, B, K)
        if x_mid <= N:
            a_max = mid
            low = mid + 1
        else:
            high = mid - 1

    if a_max == 0:
        return 0

    result = {}
    for A in range(1, a_max + 1):
        x = compute_x(A, B, K)
        if x <= N:
            result[x] = result.get(x, 0) + 1
    return result

def main():
    N, K, M = map(int, sys.stdin.readline().split())
    count = {}
    B = 1
    while True:
        x_a1 = 1
        for i in range(B + 1):
            term = 1 + i * K
            x_a1 *= term
            if x_a1 > N:
                break
        if x_a1 > N:
            break

        res = count_x(B, K, N)
        for x, cnt in res.items():
            if x in count:
                count[x] += cnt
            else:
                count[x] = cnt
        B += 1

    result = 0
    for x in count:
        if count[x] == M:
            result += 1
    print(result)

if __name__ == "__main__":
    main()
0