题目描述
blablabla
样例
def fff(a, b, p):
a1 = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % p
a2 = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % p
a3 = (a[0][1] * b[0][0] + a[1][1] * b[1][0]) % p
a4 = (a[0][1] * b[0][1] + a[1][1] * b[1][1]) % p
return [[a1, a2], [a3, a4]]
def fp(n, p):
res = [[1, 0], [0, 1]]
base = [[0, 1], [1, 1]]
while n != 0:
if n & 1:
res = fff(base, res, p)
base = fff(base, base, p)
n = n >> 1
return res[1][1] % p
# 返回第n项斐波那契数列的值
def get(n, p):
if n == 1 or n == 2: return 1
elif n==3: return 2
return fp(n - 1, p)
def s():
n, m, p = map(int, input().split())
if m==1 or m==2 or p==1:
print(0)
return
if n + 2 <= m:
v = get(n + 2, p) - 1
print(v%p)
return
n+=2
v = 0
k = n // m
s = n%m
# print(n,m,s)
if s==0:
print(get(m,p)-1)
return
kk = k // 2
if m%2==0:
if k%2==0:
v = get(n%m,p)
else:
if s%2==1:
v = get(m-s,p)
else:
v = get(m,p)-get(m-s,p)
else:
if k%2==0:
if kk%2==0:
v =get(s,p)
else:
v = get(m,p)-get(s,p)
else:
if kk%2==0:
if s % 2 == 1:
v = get(m - s, p)
else:
v = get(m, p) - get(m - s, p)
else:
if s % 2 == 1:
v = get(m, p) - get(m - s, p)
else:
v = get(m-s,p)
print((v-1)%p)
while True:
try:
s()
except:
break
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla