题目链接
问题转化
问题不妨转化为 \(a \cdot f_{n-1} + b \cdot f_n \equiv 0 \pmod m\)，要求找到最小的 \(n\) 满足这个条件。
不妨令 \(b = -b\)，则有 \(a \cdot f_{n-1} \equiv b \cdot f_n \pmod m\)
我们希望让 \(a,b,n\) 能够独立，也就是 \(a,b\) 在同一侧， \(f_n,f_{n-1}\) 在另一侧。
第一次变化
根据 \(a \equiv b \pmod m\) 等价于 \(a/d \equiv b/d \pmod {m/d}\)，我们不妨令 \(g = gcd(a,b,m)\)，则有 \(a' \cdot f_{n-1} \equiv b' \cdot f_n \pmod {m'}\)。（其中 \(a'=a/g,b'=b/g,m'=m/g\)）。
第二次变化
此时 \(gcd(a',m')\)，\(gcd(b',m')\) 都可能大于 1，也就还不能使用逆元。但是在此时，我们有 \(gcd(a',m) = gcd(f_n,m') = p\)，\(gcd(b',m')=gcd(f_{n-1},m') = q\)。
因此，式子变成了 \(\frac{a'/p}{b'/q} \equiv \frac{f_n/p}{f_{n-1}/q} \pmod{\frac{m'}{pq}}\)。我们只需要对于每一个 \(m'\)，预处理出 \(p,q,\frac{f_n/p}{f_{n-1}/q}\) 对应的答案就好了。
上面的发现可能很难注意到，这里给出证明。
我们先让 \(p = gcd(a',m')\)，\(g = gcd(f_n,m')\)。
根据 \(a \equiv b \pmod m\) 在 \(d \mid m\) 时有 \(a \equiv b \pmod d\) 这一式子，我们有 \(a' \cdot f_{n-1}\equiv b' \cdot 0 \equiv 0 \pmod {g}\)。又因为 \(f_n\) 与 \(f_{n-1}\) 互质，因此只能 \(g \mid a'\)。又因为 \(g \mid m'\)，因此有 \(g \mid gcd(a',m')\)，即 \(g \mid p\)。
同样的，我们有 \(0 \cdot f_{n-1} \equiv b' \cdot f_n \pmod {p}\)，又因为 \(gcd(b,p)=0\)，因此有 \(p \mid f_n\)。结合 \(p \mid m'\)，有 \(p \mid gcd(f_n,m')\)。也就有了 \(p \mid g\)。
因为 \(p \mid g\) 与 \(g \mid p\)，有 \(p = g\)，证毕。
时间复杂度证明
根据结论，有斐波那契数列的循环节是 \(O(m)\) 级别的，因此预处理时间复杂度是 \(O(\sum\limits_{x \mid m} x \log m)\)。单次查询是 \(\log m\) 的。
Code
这里需要注意特判 \(a = 0\) 与 \(b=0\) 的情况。并且求逆元不要用费马小定理，要用扩展欧几里得。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define File(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define LL long long
#define fi first
#define se second
const int N = 1e5 + 10;
int n,m;
map< pair<int, pair<int,int> > , int> mp[N];
void exgcd(LL a,LL b,LL &x,LL &y){if(b == 0){x = 1,y = 0;return ;}exgcd(b,a%b,y,x);y = y - a / b * x;
}
LL inv(LL a,LL b){LL x,y;exgcd(a,b,x,y);return (x + b) % b;
}
int gcd(int a,int b){if(b == 0)return a;return gcd(b,a%b);
}
void init(){for(int i=2;i<=m;i++){if(m % i == 0){int x = 0,y = 1;for(int j=1;;j++){if(x && y){int p = gcd(y,i),q = gcd(x,i);int m$ = i / p / q;int k = (y / p) * inv(x / q,m$) % m$;if(!mp[i].count({k,{q,p}})) mp[i][{k,{q,p}}] = j; }int tmpx = x,tmpy = y;x = tmpy;y = (tmpx + tmpy) % i;if(x == 0 && y == 1) break;}}}return ;
}
int main(){IOS;cin >> n >> m;init();for(int i=1;i<=n;i++){int a,b;cin >> a >> b;b = (m - b) % m;if(a == 0){cout << 0 << "\n";continue;}if(b == 0){cout << 1 << '\n';continue;}int g = gcd(gcd(a,b),m);int m$ = m / g;a /= g;b /= g;int p = gcd(a,m$),q = gcd(b,m$);int m$$ = m$ / p / q;int k = (a / p) * inv(b / q,m$$) % m$$;if(mp[m$].count({k,{q,p}}))cout << mp[m$][{k,{q,p}}] << "\n";elsecout << -1 << "\n";}return 0;
}