专栏文章

题解：P7325 [WC2021] 斐波那契

CCharllote_
P7325题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miowtsud
此快照首次捕获于
2025/12/03 02:26
3 个月前
此快照最后确认于
2025/12/03 02:26
3 个月前
查看原文

题解：P7325 [WC2021] 斐波那契

更好的阅读体验
题目传送门

题意简述

有 F0=aF_0 = a，F1=bF_1 = b，Fi=(Fi−1+Fi−2) mod mF_i = (F_{i-1} + F_{i-2}) \bmod m（i≥2i \ge 2），求 min⁡{p}\min\{p\} 使得 Fp=0F_p = 0。

规定

Fn={0 (n≤1)1 (n=1)Fn−1+Fn−2 (n≥2)F_n = \left\{\begin{aligned} 0 \space (n \le 1)\\1 \space (n=1) \\ F_{n-1}+F_{n-2} \space (n\ge 2) \end{aligned}\right.
题中序列为 GG。
(a,b,…,n)(a, b,\dots,n) 为 aa、bb 到 nn 的 gcd⁡\gcd。
a⊥ba \perp b 为 aa、bb 互质。

题目思路

首先容易发现原问题等价于求 min⁡{n}\min\{n\} 使得 aFn−1+bFn≡0(modm)aF_{n-1}+bF_n\equiv 0\pmod m。
证明：
当 n=2n = 2 时：G2=G0+G1=b=(F0a+F1b) mod mG_2 = G_0 + G_1 = b = (F_0a + F_1b) \bmod m。
当 n=3n =3 时：G3=G1+G2=a+b=(F1a+F2b) mod mG_3 = G_1+ G_2 = a + b = (F_1a+F_2b) \bmod m。
设当 n≤in \le i 时 Fn=aFn−1+bFnF_n = aF_{n-1}+bF_n 成立。
当 n=i+1n = i + 1 时：Gi+1=(Gi+Gi−1) mod m=(aFi−1+bFi+aFi−2+bFi−1) mod m=(aFi+bFi−1) mod mG_{i + 1} = (G_i + G_{i - 1}) \bmod m = (aF_{i - 1} + bF_i+aF_{i - 2} + bF_{i - 1}) \bmod m = (aF_{i}+bF_{i-1})\bmod m。
故 aFn−1+bFn≡Gn(modm)aF_{n-1}+bF_n\equiv G_n\pmod m。
为了解决原题，考虑把推导出一个形如 B≡A(modm)B\equiv A\pmod m（AA 为和 aa、bb、mm 有关的式子、BB 为和 FF 有关的式子）。
设 d=(a,b,m)d = (a, b, m)、a′=ada' = \frac{a}{d}、b′=bdb'=\frac{b}{d}、m′=mdm'=\frac{m}{d} 则 a′Fn−1+b′Fn≡0(modm′)a' F_{n-1}+b' F_n\equiv 0\pmod {m'}。
证明：
若 x≡y(modz)x \equiv y \pmod z，设 d=(x,z,y)d=(x, z, y)。
∵x mod z=(xd mod z)d\because x\bmod z = (\frac{x}{d}\bmod z)d，y mod z=(yd mod z)dy\bmod z = (\frac{y}{d}\bmod z)d，x≡y(modz)x \equiv y \pmod z。
∴(xd mod z)d≡(yd mod z)d(modz)\therefore (\frac{x}{d}\bmod z)d \equiv (\frac{y}{d}\bmod z)d \pmod z。
∴xd≡yd(modzd)\therefore \frac{x}{d} \equiv \frac{y}{d} \pmod {\frac{z}{d}}。
因为 Fn⊥Fn−1 (1)F_n \perp F_{n - 1}\space(1)，所以 (Fn,m′)=(a′,m′)=p (2)(F_n,m')=(a',m')=p\space(2)、(Fn−1,m′)=(b′,m′)=q (2)(F_{n-1},m')=(b',m')=q\space(2)。
Fn⊥Fn−1 (1)F_n \perp F_{n - 1}\space(1) 证明：
当 n=2n=2 时：F2=1,F1=1,F1⊥F2F_2 = 1, F_1=1,F_1 \perp F_2。
当 n=3n=3 时：F3=2,F2=1,F3⊥F2F_3 = 2, F_2=1,F_3 \perp F_2。
设当 n≤in\le i 时 Fn⊥Fn−1F_n \perp F_{n - 1} 成立。
当 n=i+1n = i + 1 时：
设 d=(Fi,Fi+1)d = (F_i,F_{i+1})，则：d∣Fid \mid F_i、d∣Fi+1d\mid F_{i + 1}。
∵Fn=Fn−1+Fn−2\because F_n = F_{n-1}+F_{n-2}。
∴d∣(Fi+1−Fi)=Fi−1\therefore d\mid (F_{i+1}-F_i)=F_{i-1}。
∴d=(Fi−1,Fi)=1⇒Fi+1⊥Fi\therefore d=(F_{i-1},F_i)=1\Rightarrow F_{i + 1} \perp F_i。
故 Fn⊥Fn−1F_n \perp F_{n - 1}。
(Fn,m′)=(a′,m′)=p (2)(F_n,m')=(a',m')=p\space(2)、(Fn−1,m′)=(b′,m′)=q (2)(F_{n-1},m')=(b',m')=q\space(2) 证明。
设 p=(Fn,m′)p=(F_n,m')，则 p∣Fnp\mid F_n、p∣Fn−1p\mid F_{n - 1}。
又 ∵a′Fn−1+b′Fn≡0(modm′)⇒a′Fn−1=km−b′Fn\because a' F_{n-1}+b' F_n\equiv 0\pmod {m'} \Rightarrow a' F_{n-1}=km-b' F_n。
∴p∣a′Fn−1\therefore p\mid a'F_{n-1}。
又 ∵Fn⊥Fn−1\because F_n \perp F_{n - 1}，p⊥Fnp \perp F_n。
∴p∣a′\therefore p\mid a'。
反之，设 p′=(a′,m′)p'=(a',m') 可得 p′∣Fnp'\mid F_n。
综上 (Fn,m′)=(a′,m′)=p(F_n,m')=(a',m')=p，同理 (Fn−1,m′)=(b′,m′)=q(F_{n-1},m')=(b',m')=q。
a′Fn−1+b′Fn≡0(modm′)a' F_{n-1}+b' F_n\equiv 0\pmod {m'} 两边同时除以 pqpq 得 a′pqFn−1+b′pqFn≡0(modm′pq)\frac{a'}{pq}F_{n-1}+\frac{b'}{pq} F_n\equiv 0\pmod {\frac{m'}{pq}}。易证加号两边互质，移项可得 −b′a′≡Fn−1Fn(modm′pq)-\frac{b'}{a'}\equiv \frac{F_{n-1}}{F_n}\pmod {\frac{m'}{pq}}。
由于斐波那契数列在模 mm 意义下是有循环节的，我们可以先预处理，对于每个 m′m'，计算 Fn−1Fn mod m′pq\frac{F_{n-1}}{F_n}\bmod \frac{m'}{pq}、pp、qq，并存储三元组 (p,q,Fn−1Fn  mod  m′pq)(p,q,\frac{Fn−1}{Fn} \bmod \frac{m′}{pq})。对于每组询问的 aa、bb，计算 d⁡d⁡，并得到 a′a′、b′b′、m′m′。计算 pp、qq、−b′a′ mod m′pq-\frac{b'}{a'}\bmod \frac{m'}{pq}，在存储的三元组中查找是否存在对应的项。如果存在，则找到最小的 nn 使得满足条件，如果不存在，则输出 −1−1。

AC code

CPP
#include<bits/stdc++.h> 

#define int long long 
 
using namespace std; 
 
const int N = 200000; 
 
using PPIII = pair<pair<int, int>, int>; 
int n, m, a, b; 
map<PPIII, int> ck[N + 5]; 
 
void exgcd(int a, int b, int &x, int &y) { 
    if (a == 1) { 
        x = 1; 
        y = 0; 
        return ; 
    } 
    exgcd(b, a % b, y, x); 
    y -= a / b * x; 
} 
//解方程 ax + by = 0 
 
int inv(int x, int m) { 
    int n, temp; 
    exgcd(x, m, n, temp); 
    return (n % m + m) % m; 
} 
//解同余方程求逆元 
 
signed main() { 
    ios::sync_with_stdio(false); 
    cin.tie(nullptr);  
    cin >> n >> m; 
    
    for (int i = 2; i <= m; i ++ ) 
        if (m % i == 0) { // 枚举 m' 
            int x = 1, y = 0, s = 0; 
            while (true) { // 枚举斐波那契数列 
                if (x != 0 && y != 0) { 
                    int dx = __gcd(x, i), dy = __gcd(y, i); 
                    int mp = i / dx / dy; 
                    int t = ((y / dy) * inv((x / dx), mp) % mp + mp) % mp; 
                    // 存储
                    if (!ck[i].count({{dx, dy}, t})) 
                        ck[i][{{dx, dy}, t}] = s; 
                    // 保存 
                } 
                int t = x; 
                x = y; 
                y = (t + y) % i; 
                // 计算下一对 
                if (x == 1 && y == 0) break; 
                // 循环节 
                s ++ ; 
            } 
        } 
    
    while(n -- ) { 
        cin >> a >> b; 
        b = (m - b) % m; 
        if (a == 0) { 
            cout << "0\n"; 
            continue; 
        } 
        if(b == 0) { 
            cout << "1\n"; 
            continue; 
        } 
        // 特殊判断 
        int d = __gcd(__gcd(a, b), m), mp = m / d; 
        a /= d; b /= d; 
        int p = __gcd(a, mp), q = __gcd(b, mp), mpp = mp / p / q; 
        a /= p, b /= q; 
        int k = (a * inv(b, mpp) % mpp + mpp) % mpp; 
        // 查询
        if (ck[mp].count({{q, p}, k})) 
            cout << ck[mp][{{q, p}, k}] << '\n'; 
        else 
            cout << "-1\n"; 
        // 查询答案 
    } 
    return 0; 
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...