GMOJ4015 數列

2022-09-23 05:12:21 字數 1041 閱讀 4369

分三個\(sub\)。分值分別為\(35pts,35pts,30pts\)。

\(n\leq 10^6\),直接暴力遞推即可。

\(m\leq 10^6\),顯然\(x_i\mod p\)存在長度不超過\(10^6\)的迴圈節,直接找迴圈節即可。

特殊限制\(m\in prime,2a|b,4ac=b^2-2b\),發現和二次函式很像。

不妨設二次函式\(y=ax^2+bx+c\),其中\(y\)就是\(x_i\),\(x\)就是\(x_\)。

\(2a,b,4ac\)等都與頂點式有關,所以將這個二次函式化為頂點式

\[y=a(x+\frac)^2+\frac

\]\[y=a(x+\frac)^2-\frac

\]\[y+\frac=a(x+\frac)^2

\]那麼明顯有

\[a(y+\frac)=[a(x_0+\frac)]^\]即

\[x_n=a^\times (x_0+\frac)^-\frac

\]因為\(m\)是質數,所以\(a^p\mod m=a^\mod m\)。

#include #include #include using namespace std;

typedef long long ll;

const int n=1000010;

ll x,a,b,c,n,p,t[n],vis[n];

ll power(ll x,ll k,ll mod)

void solve1()

void solve2()

vis[x]=m; t[m]=x;

x=(a*x%p*x%p+b*x%p+c)%p; }}

void solve3()

int main()