做外贸网站哪家好,教做公众号的网站,网站建设需要什么硬件和软件有哪些,快速做网站视频解析
新定义数位dp了属于是。 结论#xff1a;斐波拉契在模 10m10^m10m 的意义下循环节为 6*10^m。 但这个不一定是最小循环节#xff0c;我自己做的时候打表得出来的循环节更小。
考虑从低到高枚举周期中的位置#xff0c;暴力check合法进行剪枝。 跑的飞快#xff0c;O…解析
新定义数位dp了属于是。 结论斐波拉契在模 10m10^m10m 的意义下循环节为 6*10^m。 但这个不一定是最小循环节我自己做的时候打表得出来的循环节更小。
考虑从低到高枚举周期中的位置暴力check合法进行剪枝。 跑的飞快O能过。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define ldb long double
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Ok debug(OK\n)
using namespace std;const int N2e5100;
const int inf1e9;
//const int mod998244353
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
/*
inline ll ksm(ll x,ll k){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}*/
inline ull qm(ull x,ull y,ull mod){ll r(ldb)x*y/mod0.5,resx*y-mod*r;return res0?resmod:res;
}
struct matrix{int x,y;ull a[3][3];matrix(int X,int Y):x(X),y(Y){memset(a,0,sizeof(a));}
}tr(2,2),I(2,2);
matrix mul(const matrix u,const matrix v,ull mod){matrix res(u.x,v.y);for(int k1;ku.y;k){for(int i1;iu.x;i){ull tmpu.a[i][k];for(int j1;jv.y;j){res.a[i][j](res.a[i][j]qm(tmp,v.a[k][j],mod))%mod;}}}return res;
}
matrix ksm(matrix x,ull k,ull mod){matrix ansI;while(k){if(k1) ansmul(ans,x,mod);xmul(x,x,mod);k1;}return ans;
}
inline ull Fib(int n,ull mod){if(n0) return 0;matrix res(1,2);res.a[1][1]0;res.a[1][2]1;resmul(res,ksm(tr,n,mod),mod);return res.a[1][1];
}int n;
ull mi[20],a[20];
int top;
void dfs(int k,ull n,ull len){//printf(k%d n%llu Fib%llu\n,k,n,Fib(n,mi[k]));if(Fib(n,mi[k])!a[k]) return;if(ktop){//n6*mi[18];//printf(top%d Fib%lld %lld\n,top,Fib(n,mi[k]),a[k]);printf(%llu\n,n);exit(0);}for(int i0;i10;i){dfs(k1,(nqm(i,len,len*10)%(len*10)),len*10);}return;
}
inline int calc(ull x){int res(0);while(x){res;x/10;}return res;
}
char s[50];
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endiftr.a[1][1]0;tr.a[1][2]1;tr.a[2][1]1;tr.a[2][2]1;I.a[1][1]I.a[2][2]1;//for(int i1;i10;i) printf(%lld\n,Fib(i,998244353));scanf( %s,s1);topstrlen(s1);mi[0]1;for(int i1;i18;i) mi[i]mi[i-1]*10;for(int i1;itop;i) a[i]a[i-1](s[top-i1]-0)*mi[i-1];//for(int i1;itop;i) printf(i%d top%llu\n,i,a[i]);for(int i1;i60;i) dfs(1,i,60);puts(NIE);return 0;
}
/*
*/
