AOJ 1310 ICPC Asia resional 2010 Problem F: Find the Multiples

問題

n桁の整数が与えられる。
この整数の長さ1以上の連続する部分文字列となる整数で、Qの倍数であるようなものはいくつあるか。
ただし、部分文字列の先頭は0であってはいけない。

Qは素数である。

制約条件

n≦10^5
Q≦10^8

方針

部分文字列をa[i]a[i+1]...a[j]とする。
するとこの文字列をXとおけばXは、
a[0]+10*a[1]+...+10^k*a[k] = S[k]として、
S[i] - S[j] = 10^j * Xを満たす。
ここでXとQが互いに素であるならば、X mod Q⇔S[i] - S[j] = 0である。

ここから次のような解法が導ける。
Qが2または5でない場合は、桁を下の桁から順に見ていく。
桁ごとに、その時点までに出てきた同じ余りの数を答えに足せばいい。

Qが2または5の場合、桁を上のほうから見ていき、
Qの倍数の桁があったら、いままでに出てきた0でない数字の数だけ答えを増やす。

ソースコード

int n,s,w,q,a[100000];
void solve25(){
	ll ans=0;
	int nonzero=0;
	rep(i,n){
		if(a[i])nonzero++;
		if(a[i]%q==0)ans+=nonzero;
	}
	cout<<ans<<endl;
}
void solve(){
	ll ans=0;
	map<int,int> cnt;
	cnt[0]=1;
	ll mod=0,ten=1;
	for(int i=n-1;i>=0;i--){
		(mod+=ten*a[i])%=q;
		(ten*=10)%=q;
		if(a[i])ans+=cnt[mod];
		cnt[mod]++;
	}
	cout<<ans<<endl;
}
int main()
{
	while(scanf("%d%d%d%d",&n,&s,&w,&q),n){
		rep(i,n){
			a[i]=s/7%10;
			if(s%2==0)s/=2;
			else s=(s/2)^w;
		}
		//rep(i,n)cerr<<a[i]<<" "; cerr<<endl;
		if(q==5||q==2)solve25();
		else solve();
	}
	return 0;
}