题目链接：https://www.luogu.org/problemnew/show/P1306
做这种题，，，可真是涨姿势。
首先，得知道一个性质，否则就要爆零。gcd(F[n],F[m])=F[gcd(n,m)]，嗯，很神奇，但我不会证。
有了上面的性质，就可以拿到80分了，因为后面又加了个点，所以想要A掉还需要学更快的推斐波那契数列的方法。
据说是和矩阵有关，嗯，我还是不会。。。
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 6 const int maxn = 1e7 + 5, p = 1e8; 7 8 int f[maxn]; 9 10 int gcd(int a, int b) { 11 return b == 0 ? a : gcd(b, a % b); 12 } 13 14 int main() { 15 int n, m, g, fp, fn; 16 scanf("%d%d", &n, &m); 17 g = gcd(n, m); 18 fp = fn = 1; 19 for (int i = 3; i <= g; ++i) 20 fp = (fp + fn) % p, swap(fp, fn); 21 printf("%d", fn); 22 return 0; 23 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9829083.html
