AtCoder ABC #158 : E - Divisible Substring

本番後解いたら25分だったので出てればよかった。
https://atcoder.jp/contests/abc158/tasks/abc158_e

問題

ある整数列Sが与えられる。
この部分列のうち、(Leading Zeroを許容する)10進数とみなしたとき、素数Pの倍数であるものは何通りか。

解法

P=2とP=5の時は、1の位さえPで割れれば上は何でもよいので、Sの各位置の数値がPで割れるか判定すればよい。
それ以外の場合、ある数XがPで割れるならXを10倍したものもPで割れるはずである。
f(i) := Sの下i桁からなる10進数をPで割ったときの余り
とすると、この問題はf(i)=f(j)となるi,jの対を求める問題となる。
これは数列の部分列で総和が0となるものの組を求める典型問題と同じ要領で解ける。

int N,P;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P>>S;
	ll ret=0;
	
	if(P==2 || P==5) {
		FOR(i,N) {
			if((S[i]-'0')%P==0) ret+=(i+1);
		}
	}
	else {
		reverse(ALL(S));
		map<int,int> mp;
		mp[0]=1;
		ll cur=0,p10=1;
		FORR(c,S) {
			cur=(cur+(c-'0')*p10)%P;
			ret+=mp[cur];
			mp[cur]++;
			(p10*=10)%=P;
		}
	}
	cout<<ret<<endl;
}

まとめ

典型っぽいけどほかに出たことないのかな。