数论-斐波那契练习题二-斐波那契变式

题面

题目描述

定义一个

数列:
$f(0)=a,f(1)=b,f(n)=f(n−1)+f(n−2)f(0) = a, f(1) = b, f(n) = f(n - 1) + f(n - 2)$
$f(0)=a,f(1)=b,f(n)=f(n−1)+f(n−2)$
其中$a,b$均为正整数,$n \geq 2$问有多少种$(a,b)$,使得$k$ 出现在这个数列里,且不是前两项。由于答案可能很大,你只需要输出答案模$10^9 + 7$的结果即可。

输入输出格式

输入格式:
一行一个整数 $k$
输出格式:
一行一个数,表示答案模
$10^9 + 7$ 的结果。

输入输出样例

输入样例#1: 复制
19260817
输出样例#1: 复制
34166325
输入样例#2: 复制
1000000000
输出样例#2: 复制
773877569

说明

$1 \leq k \leq 10^9$

分析

题目大概是长成ax+by=k的形式,由于f[0]=a,f[1]=b,f[i]=f[i-1]+f[i-2] 所以可以看出在f[i]中a和b的系数是斐波那契中的相邻两项。
那么我么可以从斐波那契下手,枚举斐波那契相邻的两项,利用exgcd求出解的个数。此时依旧是对ax+by=k这个式子进行求解,此时的a等于f[i-1],b等于f[i],可以求出最小的正整数x,此时的y为最大值。可以此时的y满足
设此时的x为x0,则满足x=x0+tb,同理满足y=y0+ta,显然t+1就是此时的答案贡献,那么用最大的y除以a向上取整即可(注意之所以要向上取整而不是t+1,是因为避免y=0的情况,还有注意特判x0=0的情况)

code

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll f[100],cnt,k;
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;y=0;
return;
}
exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
}
int main()
{
scanf("%lld",&k);
f[1]=f[2]=1;cnt=2;
for(int i=3;;i++)
{
f[i]=f[i-1]+f[i-2];
if(f[i]>1e9) break;
++cnt;
}
ll ans=0;
for(int i=2;i<=cnt;++i)
{
ll a,b,x,y;
a=f[i-1];b=f[i];
exgcd(a,b,x,y);x=x*k;y=y*k;
x=(x%b+b)%b;
if(x==0) x=b;
y=(k-a*x)/b;
if(y<0) continue;
ans=(ans+(y-1)/a+1)%mod;
}
printf("%lld",ans);
}

题面

题目描述

定义一个数列:
$f(0)=a,f(1)=b,f(n)=f(n−1)+f(n−2)f(0) = a, f(1) = b, f(n) = f(n - 1) + f(n - 2)$
$f(0)=a,f(1)=b,f(n)=f(n−1)+f(n−2)$
其中$a,b$均为正整数,$n \geq 2$问有多少种$(a,b)$,使得$k$ 出现在这个数列里,且不是前两项。由于答案可能很大,你只需要输出答案模$10^9 + 7$的结果即可。

输入输出格式

输入格式:
一行一个整数 $k$
输出格式:
一行一个数,表示答案模
$10^9 + 7$ 的结果。

输入输出样例

输入样例#1: 复制
19260817
输出样例#1: 复制
34166325
输入样例#2: 复制
1000000000
输出样例#2: 复制
773877569

说明

$1 \leq k \leq 10^9$

分析

题目大概是长成ax+by=k的形式,由于f[0]=a,f[1]=b,f[i]=f[i-1]+f[i-2] 所以可以看出在f[i]中a和b的系数是斐波那契中的相邻两项。
那么我么可以从斐波那契下手,枚举斐波那契相邻的两项,利用exgcd求出解的个数。此时依旧是对ax+by=k这个式子进行求解,此时的a等于f[i-1],b等于f[i],可以求出最小的正整数x,此时的y为最大值。可以此时的y满足
设此时的x为x0,则满足x=x0+tb,同理满足y=y0+ta,显然t+1就是此时的答案贡献,那么用最大的y除以a向上取整即可(注意之所以要向上取整而不是t+1,是因为避免y=0的情况,还有注意特判x0=0的情况)

code

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll f[100],cnt,k;
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;y=0;
return;
}
exgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
}
int main()
{
scanf("%lld",&k);
f[1]=f[2]=1;cnt=2;
for(int i=3;;i++)
{
f[i]=f[i-1]+f[i-2];
if(f[i]>1e9) break;
++cnt;
}
ll ans=0;
for(int i=2;i<=cnt;++i)
{
ll a,b,x,y;
a=f[i-1];b=f[i];
exgcd(a,b,x,y);x=x*k;y=y*k;
x=(x%b+b)%b;
if(x==0) x=b;
y=(k-a*x)/b;
if(y<0) continue;
ans=(ans+(y-1)/a+1)%mod;
}
printf("%lld",ans);
}
文章目录
  1. 1. 题面
    1. 1.1. 题目描述
    2. 1.2. 输入输出格式
    3. 1.3. 输入输出样例
    4. 1.4. 说明
  2. 2. 分析
  3. 3. code
  4. 4. 题面
    1. 4.1. 题目描述
    2. 4.2. 输入输出格式
    3. 4.3. 输入输出样例
    4. 4.4. 说明
  5. 5. 分析
  6. 6. code