#614939 (PyPy3) No.1383 Numbers of Product

• 問題: No.1383 Numbers of Product
• ユーザー: 👑 SPD_9X2
• 提出日時: 2021-02-07 22:00:22
• 言語: PyPy3 (7.3.15)
• 結果: TLE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 2,449 bytes
• コンパイル時間: 145 ms
• コンパイル使用メモリ: 82,196 KB
• 実行使用メモリ: 226,472 KB
• 最終ジャッジ日時: 2024-07-04 15:29:32
• 合計ジャッジ時間: 46,309 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

ファイルパターン	結果
sample	AC * 2
other	AC * 47 TLE * 4

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
"""
Aで場合分けしたい!!
AはX以下
Bはあまり大きくならない
Bに関してAを二分探索
B = 1の時
A * (A+K) がすでに多いのが嫌だ
B = 2以上の場合は
列挙可能
列挙した後、M個の奴 or M-1個のやつに関して
B=1があるかを判定すればよい
Aを二分探索すれば見つかる
M = 1の場合だけ嫌だな
別で処理する
A*(A+K)の中で、バッティングした数を覚えておく
それ以外の A*(A+K)
"""
import sys
import heapq
from collections import deque
from sys import stdin
def want(A,B):
    ret = A
    for i in range(B):
        ret *= A + (i+1)*K
    return ret
dic = {}
N,K,M = map(int,stdin.readline().split())
if M != 1:
    # B >= 2 の全列挙
    for B in range(2,22):
        for A in range(1,10**9):
            X = want(A,B)
            if X <= N:
                if X not in dic:
                    dic[X] = 1
                else:
                    dic[X] += 1
            else:
                break
    ans = 0
    #B = 1があるかを検索
    for X in dic:
        
        if M-1 <= dic[X] <= M:
            l = 0
            r = 10**18
            while r-l != 1:
                m = (l+r)//2
                if m*(m+K) <= X:
                    l = m
                else:
                    r = m
            if l*(l+K) == X:
                dic[X] += 1
            if dic[X] == M:
                ans += 1
    print (ans)
else: #M==1の場合
    # B >= 2 の全列挙
    for B in range(2,22):
        for A in range(1,10**9):
            X = want(A,B)
            if X <= N:
                if X not in dic:
                    dic[X] = 1
                else:
                    dic[X] += 1
            else:
                break
    ans = 0
    bat = 0
    
    #B = 1があるかを検索
    #print (dic)
    for X in dic:
        
        l = 0
        r = 10**18
        while r-l != 1:
            m = (l+r)//2
            if m*(m+K) <= X:
                l = m
            else:
                r = m
        #print (X,l,K)
        if l*(l+K) == X:
            bat += 1
            dic[X] += 1
        if dic[X] == M:
            ans += 1
    #print (ans,bat,file=sys.stderr)
    
    #有効な最大のAを求める
    l = 0
    r = 10**18
    while r-l != 1:
        m = (l+r)//2
        if m * (m+K) <= N:
            l = m
        else:
            r = m
    ans += l - bat
    print (ans)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX