Codeforces #885 : Div2 E. Vika and Stone Skipping

この回難易度がF＜D＜Eだな。
https://codeforces.com/contest/1848/problem/E

問題

強さFで海に向かって石を投げたとき、距離F,F+(F-1),F+(F-1)+(F-2),…の位置でバウンドする。
距離Xが与えられるので、XでバウンドするFは何通りあるか答えよ。

クエリとして、Xが毎回指定された値だけ整数倍されるので、その都度上記問題にこたえよ。

解法

Xのうち奇数の約数の数が解となる。
よってXを素因数分解し、奇素数の(次数+1)の積を計算しよう。

ll X;
int Q;
ll mo;

map<int,int> M;
ll ret;
int num;

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;
}

void hoge(int n) {
	int a=n+1;
	while(a%mo==0) a/=mo, num++;
	while(n%mo==0) n/=mo, num--;
	ret=ret*a%mo*modpow(n)%mo;
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Q>>mo;
	while(X%2==0) X/=2;
	ret=1;
	for(i=2;i*i<=X;i++) while(X%i==0) {
		X/=i;
		hoge(++M[i]);
	}
	if(X>1) {
		hoge(++M[X]);
	}
	while(Q--) {
		cin>>X;
		while(X%2==0) X/=2;
		for(i=2;i*i<=X;i++) while(X%i==0) {
			X/=i;
			hoge(++M[i]);
		}
		if(X>1) {
			hoge(++M[X]);
		}
		
		if(num) {
			cout<<0<<endl;
		}
		else {
			cout<<ret<<endl;
		}
	}
	
	
}

まとめ

Mが小さいときの対応が本質的でなくて余りすきではないな…。