通过这个题目发现了一个很奇妙的性质 \[gcd(fib(a),fib(b))=fib(gcd(a,b))\] 这样只需要枚举下标的公因数，然后看看有没有\(k\)个符合条件就可以了。 注意，因为是通过\(\frac{r}{p}-\frac{l-1}{p}\)判断的。而本质不同的\(\frac{r}{p}\)只有\(\sqrt{r}\)级别，所以只需要枚举\(\sqrt{r}\)次即可，枚举\(\frac{r}{p}\)相同的最大的\(p\)
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
58
59
60
61
62
63
64
65
66
| #include<bits/stdc++.h>
typedef long long LL;
using namespace std;
LL m,a,b,k;
struct oo{
LL t[2][2];
};
oo su;
oo tt;
oo cheng(oo x,oo y)
{
oo ans;
for(int i=0;i<=1;i++)
{
for(int j=0;j<=1;j++)
{
ans.t[i][j]=0;
for(int k=0;k<=1;k++)
{
ans.t[i][j]+=x.t[i][k]*y.t[k][j];
ans.t[i][j]%=m;
}
}
}
return ans;
}
oo kpow(LL x)
{
if(x==0) return su;
oo ans=kpow(x/2);
ans=cheng(ans,ans);
if(x%2) ans=cheng(ans,tt);
return ans;
}
LL ff(LL x)
{
su.t[0][1]=0;
su.t[0][0]=1;
su.t[1][0]=0;
su.t[1][1]=1;
tt.t[0][0]=0;
tt.t[0][1]=1;
tt.t[1][0]=1;
tt.t[1][1]=1;
if(x==1) return 1%m;
oo p=kpow(x-2);
LL ans=p.t[0][1]+p.t[1][1];
ans%=m;
return ans;
}
int main()
{
scanf("%I64d%I64d%I64d%I64d",&m,&b,&a,&k);
LL ans=0,pos;
pos=a/k;
while(pos>=1)
{
LL pp=a/pos-(b-1)/pos;
if(pp>=k) ans=max(pos,ans);
pos=a/(a/pos+1);
}
printf("%I64d",ff(ans));
return 0;
}
|