「CF1264F」Beautiful Fibonacci Problem

对于长度为 $n$ 的递增等差正整数序列 $\{a, a+d, a+2d \ldots a+(n-1)d\}$，我们用三元组 $(a,d,n)$ 表示。

给定递增等差正整数序列 $(a,d,n)$，你需要构造递增等差正整数序列 $(b,e,n)$，满足：

• $b,e < 2^{64}$，且是正整数
• 对于所有 $0 \leq i < n$，$a+id$ 的十进制表示是 $F_{b+ie}$ 的十进制表示的后 $18$ 位的子串（如果没有 $18$ 位自动补前导零）。其中 $F_i$ 是指斐波那契数列的第 $i$ 项。

$1 \leq a+(n-1)d \leq 10^6$。

题解

设 $P = 10^6$，则有 $\pi(P) \mid 6P$，尝试得取 $n = 3P$ 是 $\bmod P$ 意义下的周期。

则有 $F_{n} \equiv 0 \pmod P$，$F_{n+1} \equiv 1 \pmod P$。考虑：

• $F_{2n+1} \equiv F_n^2 + F_{n+1}^2 \equiv F_{n+1}^2 \pmod {P^2}$
• $F_{3n+1} \equiv F_n F_{2n} + F_{n+1} F_{2n+1} \equiv F_{n+1}^3 \pmod {P^2}$
• $\ldots$
• $F_{kn+1} \equiv F_{n+1}^k \pmod {P^2}$

此例中，我们有 $F_{n+1} \equiv 2 t P + 1 \pmod P^2$，其中 $t$ 是与 $P$ 互质的整数。

则 $F_{kn+1} \equiv F_{n+1}^k \equiv 2kt P + 1$，取 $k = 5 k’ t^{-1}$，则枚举 $1 \leq k’ < 10^6$ 即可解决本题。

代码（Python）

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

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)