啦啦啦啦啦啦啦啦啦啦

懵逼的 题目

BZOJ

扯淡的 题解

首先我们要知道一个结论 叫斐波那契数模$10^n$的循环周期是$6 \times 10^n$1

然后呢 我们就可以从低到高的搜索$s$ 因为有循环 所以我们只需要检验上一个$k$加上任意个$6 \times 10^{dq}$所在的斐波那契树的$dq$位是否是我们搜的这一位就行了

沙茶的 代码

抄抄抄

#include<cstdio>
#include<cstring>
#define N 20
typedef long long ll;
typedef unsigned long long ull;
int n,i,flag;char a[N];ll mo[N],b[N];ull ans;
inline ull mul(ull a,ull b,ull P){ull t=0;for(;b;b>>=1,a=(a+a)%P)if(b&1)t=(t+a)%P;return t;}
void cal(ll n,ll&x,ll&y,ll P){
  if(!n){x=0,y=1;return;}
  if(n==1){x=y=1;return;}
  if(n&1){
    cal(n-1,y,x,P);
    y=(1ULL*y+x)%P;
    return;
  }
  ll a,b;
  cal(n>>1,a,b,P);
  x=(mul(a,b,P)+mul(a,b<a?b-a+P:b-a,P))%P;
  y=(mul(a,a,P)+mul(b,b,P))%P;
}
inline ll fib(ll n,ll P){ll x,y;cal(n,x,y,P);return x;}
void dfs(int n,ll t,ll T){
  if(flag)return;
  if(fib(t,mo[n])!=b[n])return;
  if(n==1){flag=1,ans=6000000000000000000ULL+t;return;}
  for(int i=0;i<10;i++)dfs(n-1,(1ULL*t+T*i)%(T*10),T*10);
}
int main(){
  scanf("%s",a+1),n=strlen(a+1);
  for(mo[i=n]=1;i;i--,mo[i]=mo[i+1]*10)b[i]=mo[i]*(a[i]-'0')+b[i+1];
  for(i=1;i<=n;i++)mo[i]*=10;
  for(i=0;i<60;i++)dfs(n,i,60);
  if(flag)printf("%llu",ans);else puts("NIE");
  return 0;
}

By 准备退役旅游的 Cansult


  1. 1.其实更普遍的情况是模$A^x$的循环节$L(A^x)$是$A^{x - 1} \cdot L(A)$