【BSGS】【数论】TopCoder15277 WrongBase

题意：

还是那个船长写的题意：

分析：

首先，已知的是：
$Y_i\equiv g^{x_i}$
然后要求$h^{x_i}$，如果算出$T(h=g^T)$
那么$h^{x_i}=g^{T\times x_i}=Y_i^T$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#define SF scanf
#define PF printf
#define MAXN 1000010
#define MOD 998244353
using namespace std;
typedef long long ll;
ll fsp(ll x,int y){
    ll res=1;while(y){
    if(y&1)res=res*x%MOD;x=x*x%MOD;y>>=1;}return res;
}
ll x[MAXN],y[MAXN];
int M;
unordered_map<ll,int> mp;
void prepare(ll g){
    ll e=fsp(g,M);ll e1=1;for(int i=0;i<=MOD-1;i+=M){
    mp[e1]=i;e1=e*e1%MOD;}
}
ll query(ll X,ll g){
    ll e=fsp(g,MOD-2);ll e0=1;for(int i=0;i<M;i++){
    ll tar=X*e0%MOD;	e0=e0*e%MOD;if(mp.count(tar))return mp[tar]+i;}return -1;
}
int main(){
    
// freopen("contingency.in","r",stdin);
// freopen("contingency.out","w",stdout);ll h,a,d,g;int n;M=int(sqrt(MOD-1));SF("%lld%lld%lld%lld%d",&g,&h,&a,&d,&n);if(h==0){
    PF("0");return 0;}prepare(g);y[1]=a;for(int i=2;i<=n;i++)y[i]=y[i-1]+d;ll t=query(h,g);ll sum=0;for(int i=1;i<=n;i++)sum=(sum+fsp(y[i],t))%MOD;PF("%lld",sum);
}