結果

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

ソースコード

diff # 

import sys
import math

def count_x(B, K, N):
    if B == 0:
        return N
    low = 1
    high = min(N // 1, 2 * 10**18)
    best = 0
    while low <= high:
        mid = (low + high) // 2
        product = 1
        a = mid
        for i in range(B + 1):
            if product > N:
                break
            product *= (a + i * K)
            if product > N:
                break
        if product <= N:
            best = mid
            low = mid + 1
        else:
            high = mid - 1
    if best == 0:
        return 0
    else:
        return best

def main():
    N, K, M = map(int, sys.stdin.readline().split())
    B_max = 0
    a = 1
    product = 1
    while True:
        product *= (a + B_max * K)
        if product > N or B_max > 100:
            break
        B_max += 1
    B_max -= 1
    count_dict = {}
    for B in range(0, B_max + 1):
        if B == 0:
            if M >= 1:
                possible_x = N
                if M == 1:
                    if possible_x not in count_dict:
                        count_dict[possible_x] = 0
                    count_dict[possible_x] += 1
            continue
        max_a = count_x(B, K, N)
        if max_a == 0:
            continue
        for a in range(1, max_a + 1):
            product = 1
            for i in range(B + 1):
                term = a + i * K
                product *= term
                if product > N:
                    break
            if product > N:
                break
            if product in count_dict:
                count_dict[product] += 1
            else:
                count_dict[product] = 1
    result = 0
    for x in count_dict:
        if count_dict[x] == M:
            result += 1
    print(result)

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