「Luogu P1306」斐波那契公约数 - 数论 + 矩阵加速

给定正整数 `n` 和 `m`

Fibonacci数列第 `n` 项和第 `m` 项的最大公因数

`n,m \le 10^9`

链接

「Luogu P1306」

题解

结论

$$ gcd(F[n], F[m]) = F[gcd(n, m)] $$

证明

对于`n<m`,我们设`F[n] = a`,`F[n+1] = b`

则`F[n+2] = a+b`,`F[n+3] = a+2 \times b`

归纳一下得`F[m] = F[m-n-1] \times a + F[m-n] \times b`

所以`gcd(F[n], F[m]) = gcd(F[n], F[m-n-1] \times a + F[m-n] \times b)`

将`F[n] = a`,`F[n+1] = b`代入

得`gcd(F[n], F[m]) = gcd(F[n], F[m-n-1] \times F[n] + F[m-n] \times F[n+1])`

所以`gcd(F[n], F[m]) = gcd(F[n], F[m-n] \times F[n+1])`

因为`gcd(F[n], F[n+1]) = 1`

所以`gcd(F[n], F[m]) = gcd(F[n], F[m-n])`

所以`gcd(F[n], F[m]) = gcd(F[n], F[m \bmod n])`

所以`gcd(F[n], F[m]) = F[gcd(n, m)]`

代码

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <memory.h>
#include <stdio.h>

typedef long long LL;

const int N = 2;
const int P = 1e8;

LL n, m;

struct Matrix
{
LL a[N + 5][N + 5];
Matrix() { memset(a, 0, sizeof(a)); }
Matrix friend operator*(Matrix X, Matrix Y)
{
Matrix Z;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
for (int k = 1; k <= N; k++)
Z.a[i][j] = (Z.a[i][j] + X.a[i][k] * Y.a[k][j] % P) % P;
return Z;
}
} ans, base;

Matrix pow(Matrix base, LL k)
{
while (k)
{
if (k & 1)
ans = ans * base;
base = base * base;
k >>= 1;
}
return ans;
}

LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}

int main()
{
scanf("%lld%lld", &n, &m);
n = gcd(n, m);
if (n <= 2)
{
printf("1");
return 0;
}
ans.a[1][1] = ans.a[1][2] = 1;
base.a[1][1] = base.a[1][2] = base.a[2][1] = 1;
ans = pow(base, n - 2);
printf("%lld", ans.a[1][1]);
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×