結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def compute_X(A, K, B, N):
    product = 1
    for i in range(B + 1):
        term = A + i * K
        if product > N // term:
            return N + 1  # 超过N
        product *= term
        if product > N:
            return product
    return product

def find_A_max(B, K, N):
    # 计算X_min=1*(1+K)*(1+2K)*...*(1+BK)
    X_min = 1
    for i in range(B + 1):
        X_min *= (1 + i * K)
        if X_min > N:
            return 0
    if X_min > N:
        return 0
    
    low = 1
    high = N  # 初始设置为N，可能太大，但二分法会自动调整
    best = 0
    while low <= high:
        mid = (low + high) // 2
        x = compute_X(mid, K, B, N)
        if x <= N:
            best = mid
            low = mid + 1
        else:
            high = mid - 1
    return best

def main():
    N, K, M = map(int, sys.stdin.readline().split())
    counts = defaultdict(int)
    B = 1  # B必须>=1
    while True:
        # 计算X_min = 1*(1+K)*...*(1+BK)
        X_min = 1
        for i in range(B + 1):
            X_min *= (1 + i * K)
            if X_min > N:
                break
        if X_min > N:
            break  # X_min超过N，停止枚举更大的B
        
        # 找到最大的A_max
        A_max = find_A_max(B, K, N)
        if A_max == 0:
            B += 1
            continue
        # 处理A=1到A_max的情况
        for A in range(1, A_max + 1):
            x = compute_X(A, K, B, N)
            if x <= N:
                counts[x] += 1
        B += 1
    
    # 统计结果
    result = 0
    for x in counts:
        if counts[x] == M:
            result += 1
    print(result)

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