用三元组 表示长度为 的递增等差正整数序列 。给定 ,要求构造 满足:
- ,且是正整数
- 对于所有 , 的十进制表示是 的十进制表示的后 位的子串(如果没有 位自动补前导零)。其中 是指斐波那契数列的第 项。
。
题解
设 ,则有 ,尝试得取 是 意义下的周期。
则有 ,。考虑:
此例中,我们有 ,其中 是与 互质的整数。
则 ,取 ,则枚举 即可解决本题。
代码
def exgcd(a, b):
if b == 0:
return 1, 0
x, y = exgcd(b, a % b)
return y, x - y * (a // b)
def inv(a, p):
x, y = exgcd(a, p)
return (x % p + p) % p
def xmul(a, b):
c = [[0, 0], [0, 0]]
for i in range(0, 2):
for j in range(0, 2):
for k in range(0, 2):
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % (10**12)
return c
def xpow(a, b):
s = [[1, 0], [0, 1]]
while b:
if b % 2:
s = xmul(s, a)
a = xmul(a, a)
b //= 2
return s
def fib(n):
if n <= 1:
return n
return xmul([[1, 0], [0, 0]], xpow([[1, 1], [1, 0]], n - 1))[0][0]
if __name__ == "__main__":
t = fib(3 * (10**6) + 1) // (10**6)
u = 15 * inv(t // 2, 10**6)
n, a, d = map(int, input().split())
b = a * u * (10**6) + 1
e = d * u * (10**6)
print(b, e)