正題

題目鏈接:https://jzoj.net/senior/#contest/show/3011/0

---

題目大意

給出$n,m,a,b,c,x_0$
$$x_i=a{x}_{i?1}^2+b{x}_{i?1}+c$$

求$x_n\%m$

---

解題思路

第一段$n\le 1e6$直接$O(n)$暴力做
第二段$m\le 1e6$找到一個循環(huán)節(jié)然后在套到n里
第三段:
$$x_i=a{x}_{i?1}^2+b{x}_{i?1}+c$$
學過二次函數(shù)的對于給出的性質有敏銳的直覺
$$x_i=a(x+\frac{b}{2a}{)}^2+\frac{4ac?b^2}{4a}$$
$4ac=b^2?2b?4ac?b^2=2b$
$$x_i=a(x+\frac{b}{2a}{)}^2?\frac{b}{2a}$$
然后定義$k=\frac{b}{2a}$
$$x_i+k=a(x+k{)}^2$$
同時乘上$a$
$$a(x_i+k)=(a(x+k){)}^2$$
定義$y_i=a(x_i+k)$
那么有$$y_i=y_{i?1}^2$$
即$$y_n=y_0^{2^n}$$

用費馬小可以讓指數(shù)摸上$m?1$計算出$y_n$，然后倒推出$x_n$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll M=1e6+10; ll n,m,a,b,c,x,fa[M],cir[M],v[M]; void solve1(){for(ll i=1;i<=n;i++)x=(a*x%m*x%m+b*x%m+c)%m;printf("%lld",x); } void solve2(){x%=m;for(ll i=0;i<=m;i++)fa[i]=(a*i%m*i%m+b*i%m+c)%m;ll cnt=0;cir[0]=x;v[x]=1;while(!v[x=fa[x]])cir[++cnt]=x,v[x]=cnt;x=v[x];if(n<=cnt) printf("%lld",cir[n]);else{n-=x;printf("%lld",cir[x+n%(cnt-x+1)]);} } ll power(ll x,ll b,ll p){ll ans=1;while(b){if(b&1) ans=ans*x%p;x=x*x%p;b>>=1;}return ans; } void solve3(){ll z=b/2/a,y=a*(x+z)%m;y=power(y,power(2,n,m-1),m);printf("%lld",(y*power(a,m-2,m)%m-z+m)%m); } int main() {scanf("%lld%lld%lld%lld%lld%lld",&x,&a,&b,&c,&n,&m);x=x%m;a%=m;b%=m;c%=m;if(n<=1e6)solve1();else if(m<=1e6)solve2();else solve3(); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的jzoj4015-数列【循环节,数论】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。