#1031331 (PyPy3) No.2989 Fibonacci Prize

• 問題: No.2989 Fibonacci Prize
• ユーザー: titia
• 提出日時: 2024-12-14 05:37:33
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 358 ms / 2,000 ms
• コード長: 1,621 bytes
• コンパイル時間: 373 ms
• コンパイル使用メモリ: 82,240 KB
• 実行使用メモリ: 167,232 KB
• 最終ジャッジ日時: 2024-12-14 05:37:46
• 合計ジャッジ時間: 11,644 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 77

ソースコード

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
N,M=map(int,input().split())
if M<=100:
    F=[1,1]
    for i in range(M+3):
        F.append(F[-1]+F[-2])
    MAX=F[M-1]
    ANS=0
    for i in range(M+3):
        now=0
        for j in range(i,M+3):
            now+=F[j]
            if now%N==0 and now<=MAX:
                #print(i,j)
                ANS+=1
    print(ANS)
    exit()
if N!=1:
    F=[0,1]
    while True:
        F.append((F[-1]+F[-2])%N)
        if F[-2]==0 and F[-1]==1:
            break
    F=F[1:-1]
else:
    F=[0]
    
LIST=[[0]]
LIST=[[] for i in range(N)]
for i in range(len(F)):
    LIST[F[i]].append(i)
# 和がF[M-1]以下
# F[x]～F[y]
# = F[y+2] - F[x+1]
# y=M-1のとき
# x=M-1のときのみOK
# y=M-2のとき、
# x=M-3のとき、F[M] - F[M-2] = F[M-1]でOK
# なので、x=y-1かy
# y=M-3のとき、何でもOK
# y+1を全探索する。
# y<=M-3のとき、y+2<=M-1
# x<=M-3なので、x+1<=M-2
# なので、[0,M-1]で正しいものを計算し、例外として、y=M-1,M-2のときを調べる。
ANS=0
rep=(M-1)//len(F)
for i in range(N):
    L=LIST[i]
    ko=rep*len(L)
    for j in range(len(L)):
        if L[j]+rep*len(F)<=M-1:
            ko+=1
        else:
            break
    #print("!",ANS,ko)
        
    ANS+=ko*(ko-1)//2
    if L and L[0]==0:
        ANS-=ko-1
#print(ANS)
y=(M+1)%len(F)
x=M%len(F)
for i in range(N):
    if x in LIST[i] and y in LIST[i]:
        ANS+=1
#print(ANS)
y=M%len(F)
for i in range(N):
    if y in LIST[i]:
        if (y-1)%len(F) in LIST[i]:
            ANS+=1
        if (y-2)%len(F) in LIST[i]:
            ANS+=1
print(ANS)
    
            
    
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX