TopCoder SRM 751 Div1 Medium WrongBase

ひっかけさえなければ…。
https://community.topcoder.com/stat?c=problem_statement&pm=15277

問題

ある素数M=998244533において、pow(g,499122176)、pow(g,142606336)、pow(g,58720256)におけるMの剰余が一致しないようなgが与えられる。
今、ある整数列Xに対し、pow(g,X[0])、pow(g,X[1])....が与えられる。
X自体は直接は与えられない。

この時整数hに対し、pow(h,X[0])、pow(h,X[1])....を求めその和を求めよ。

解法

h=0の場合、解は0。以下hが0以外である場合を考える。

M-1=(2^23)*7*17であり、問題文よりpow(g,(M-1)/2)、pow(g,(M-1)/7)、pow(g,(M-1)/17)が一致しないということはgは原始根であることがわかる。
よってpow(g,y)=h (mod M)となるようなyが存在する。
その時、pow(h,X[0])=pow(pow(g,y),X[0])=pow(pow(g,X[0]),y)となるので、与えられるpow(g,X[0])、pow(g,X[1])....をそれぞれy乗すれば解になる。
yを求めるのは、離散対数問題なのでBaby-Step Giant-Stepでよい。

ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class WrongBase {
	public:
	int modlog(int g,int a) {  // return g^x=a mod a
		map<int,int> M;
		ll cur=1;
		int sq=sqrt(mo);
		int i;
		FOR(i,sq) {
			M[cur]=i;
			cur=cur*g%mo;
		}
		
		ll step=cur;
		cur=1;
		ll num=0;
		while(1) {
			ll x=a*modpow(cur)%mo;
			if(M.count(x)) return num+M[x];
			cur=cur*step%mo;
			num+=sq;
		}
	}
	
	int getSum(int g, int h, int a, int d, int n) {
		if(h==0) return 0;
		
		ll x=modlog(g,h);
		ll sum=0;
		int i;
		FOR(i,n) {
			sum+=modpow(a,x);
			a+=d;
		}
		return sum%mo;
	}
}

まとめ

h=0を見事に見落とした。