Codeforces 227E/226C Anniversary 斐波那契数列性质+矩阵快速幂

这只梓喵是我洛谷博客的背景.

我们来看一下这题.

题目翻译

给出l,r,k,在区间[l,r]中找k个不同数字使得以这些数字为下标的斐波那契数的最大公约数最大.
输出最大值模m的值.

胡搞毛搞

我一看可高兴了,觉得此题非常可做.首先我们考虑斐波那契数列F(n)$F(n)$ 的一个性质:
gcd(F(a),F(b))=F(gcd(a,b))$gcd(F(a),F(b))=F(gcd(a,b))$
我记得这个性质是我从哪里知道的来着?
luogu p1306 斐波那契公约数
然后只要找到最大的x$x$使得x$x$的倍数在[l,r]$[l,r]$里大于或者等于k$k$个即可.
猜猜这个x$x$能不能二分?
这里我不得不把我自己批一顿.
我竟然对不能二分的东西写了二分,而且一开始以为自己二分萎了后来才发现根本不能二分,调了5个小时!
假设存在一个数字q$q$,对于q−1$q-1$来说,它在[l,r]$[l,r]$内的倍数的个数变化了,这样的q$q$存在(√r)$\sqrt{(}r)$个.
根据数据范围我们用n−−√$\sqrt{n}$ 的枚举.由于我们要求的只是最大值,我们只需要对于r√$\sqrt{r}$之内的每一个i$i$判断i$i$和r/i$r/i$ 的倍数在[l,r]$[l,r]$是不是大于或者等于k$k$个即可.
这样可以求出ans$ans$,答案就是第ans$ans$个斐波那契数,用矩阵快速幂即可.

#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) x=-x,pc('-');
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int mod=read();
ll l,r,k;

bool judge(ll x){
return r/x-(l-1)/x>=k;
}

struct juzhen{
ll m[3][3];
void clearit(){
  memset(m,0,sizeof m);
  m[1][1]=m[2][2]=1;
  }
void clear(){memset(m,0,sizeof m);}
juzhen operator *(const juzhen &b) const{
  int i,j,k;
  juzhen ans;ans.clear();
  for (i=1;i<3;++i){
    for (j=1;j<3;++j){
      for (k=1;k<3;++k){
        ans.m[i][j]=(ans.m[i][j]+m[i][k]*b.m[k][j])%mod;
        } 
      }
    }return ans;
  }
};

juzhen operator ^(juzhen a,ll b){
juzhen c;c.clearit();
for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
return c;
}

int main(){
read(l),read(r),read(k);
ll ans=0;
for (ll i=1;i*i<=r;++i){
  if (judge(i)) ans=max(ans,i);
  if (judge(r/i)) ans=max(ans,r/i); 
  }
juzhen tmp;
tmp.clear();
tmp.m[1][1]=tmp.m[1][2]=tmp.m[2][1]=1;
tmp=tmp^ans-1;
write((tmp.m[1][1]+mod)%mod);
}
/*
gcd(F(a),F(b))=F(gcd(a,b));
*/

谢谢大家.