QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#671140 | #9225. Fibonacci Fusion | Legend_dy | RE | 7ms | 10744kb | Python3 | 1.5kb | 2024-10-24 11:12:22 | 2024-10-24 11:12:23 |
Judging History
answer
import math
sq5 = math.sqrt(5)
P = 1000000000000002097
fio = [0, 1]
for i in range(50):
fio.append((fio[-1] + fio[-2]) % P)
def mul(m1, m2):
m3 = [[0, 0], [0, 0]]
for i in range(0, 2):
for j in range(0, 2):
for k in range(0, 2):
m3[i][j] = (m3[i][j] + m1[i][k] * m2[k][j] % P) % P
return m3
def Fio(n):
if n <= 20:
return fio[n]
y = [[1, 0], [0, 1]]
x = [[0, 1], [1, 1]]
while n > 0:
if n % 2 == 1:
y = mul(y, x)
x = mul(x, x)
n //= 2
return y[1][0]
def get(x):
if x <= 20:
y = 1
while True:
if fio[y] >= x:
return y
y += 1
return math.ceil((math.log10(sq5) + math.log10(x)) / math.log10((1 + sq5) / 2))
n = int(input())
a = []
for i in range(0, n):
a.append(int(input()))
# a.append(Fio(21) - 11)
# a.append(Fio(20) - 23)
# a.append(Fio(20) - 31)
# a.append(11)
# a.append(23)
# a.append(31)
a = sorted(a)
ans = 0
mp = {-1:0}
# k = get(10 ** 2000000)
# print(k)
# print(Fio(20))
# print(Fio(21))
for j in range(0, n):
i = get(a[j])
a[j] %= P
ans += mp.get((Fio(i) - a[j] + P) % P, 0)
ans += mp.get((Fio(i + 1) - a[j] + P) % P, 0)
ans += mp.get((Fio(i + 2) - a[j] + P) % P, 0)
ans += mp.get((Fio(i + 3) - a[j] + P) % P, 0)
if mp.get(a[j], 0) == 0:
mp.update({a[j]:1})
else:
mp[a[j]] += 1
print(ans)
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 10744kb
input:
6 50 8 8 5 72 354224848179261915070
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: -100
Dangerous Syscalls
input:
28 200878223506436882933619847964496455022155117513398820563747455993172799881403389571477889821109288771413214004090719097929400406252135763028179112130390003528046316900603668569910008417315162907579003880220844686222148696041857432602133894827753998572080650383305777912447151917272483538029469449...