結果

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

ソースコード

diff # 

import sys

def main():
    import math
    N, K, M = map(int, sys.stdin.readline().split())
    if M == 0:
        print(N)
        return
    
    max_B = 0
    current = 1
    while True:
        next_term = current * (1 + max_B * K)
        if next_term > N:
            break
        current = next_term
        max_B += 1
        if max_B > 60:
            break
    
    freq = dict()
    
    for B in range(1, max_B + 1):
        terms = B + 1
        minimal = 1
        for i in range(terms):
            minimal *= (1 + i * K)
        if minimal > N:
            continue
        
        low = 1
        high = 1
        while True:
            val = 1
            a = high
            for i in range(terms):
                val *= (a + i * K)
                if val > N:
                    break
            if val > N:
                break
            high *= 2
        
        max_A = 0
        low = 1
        high = high // 2
        while low <= high:
            mid = (low + high) // 2
            val = 1
            a = mid
            for i in range(terms):
                val *= (a + i * K)
                if val > N:
                    break
            if val <= N:
                max_A = mid
                low = mid + 1
            else:
                high = mid - 1
        
        if max_A == 0:
            continue
        
        for A in range(1, max_A + 1):
            x = 1
            a = A
            for i in range(terms):
                x *= (a + i * K)
                if x > N:
                    break
            if x > N:
                break
            if x not in freq:
                freq[x] = 0
            freq[x] += 1
    
    count = 0
    for x in freq:
        if freq[x] == M:
            count += 1
    print(count)

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