「CF1264F」Beautiful Fibonacci Problem
「CF1264F」Beautiful Fibonacci Problem

2020 年 09 月 17 日

用三元组 (a,d,n)(a,d,n) 表示长度为 nn 的递增等差正整数序列 {a,a+d,a+2da+(n1)d}\{a, a+d, a+2d \ldots a+(n-1)d\}。给定 (a,d,n)(a,d,n),要求构造 (b,e,n)(b,e,n) 满足:

  • b,e<264b,e < 2^{64},且是正整数
  • 对于所有 0i<n0 \leq i < na+ida+id 的十进制表示是 Fb+ieF_{b+ie} 的十进制表示的后 1818 位的子串(如果没有 1818 位自动补前导零)。其中 FiF_i 是指斐波那契数列的第 ii 项。

1a+(n1)d1061 \leq a+(n-1)d \leq 10^6

题解

P=106P = 10^6,则有 π(P)6P\pi(P) \mid 6P,尝试得取 n=3Pn = 3PmodP\bmod P 意义下的周期。

则有 Fn0(modP)F_{n} \equiv 0 \pmod PFn+11(modP)F_{n+1} \equiv 1 \pmod P。考虑:

  • F2n+1Fn2+Fn+12Fn+12(modP2)F_{2n+1} \equiv F_n^2 + F_{n+1}^2 \equiv F_{n+1}^2 \pmod {P^2}
  • F3n+1FnF2n+Fn+1F2n+1Fn+13(modP2)F_{3n+1} \equiv F_n F_{2n} + F_{n+1} F_{2n+1} \equiv F_{n+1}^3 \pmod {P^2}
  • \ldots
  • Fkn+1Fn+1k(modP2)F_{kn+1} \equiv F_{n+1}^k \pmod {P^2}

此例中,我们有 Fn+12tP+1(modP)2F_{n+1} \equiv 2 t P + 1 \pmod P^2,其中 tt 是与 PP 互质的整数。

Fkn+1Fn+1k2ktP+1F_{kn+1} \equiv F_{n+1}^k \equiv 2kt P + 1,取 k=5kt1k = 5 k' t^{-1},则枚举 1k<1061 \leq k' < 10^6 即可解决本题。

代码

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)

评论

TABLE OF CONTENTS

题解