Codeforces #279 Div2 C. Hacking Cypher

CF279に参加。
ABCDEまで順調に解いたものの、Fで大ざっぱなTLE解を投げてしまった。
http://codeforces.com/contest/490/problem/C

問題

L桁の数値Nが与えられる。
この数値を前半と後半に２分割し、前半をaの倍数、後半をbの倍数とするようにしたい。
そのような分け方ができるか。

なお、分割後の数値はleading zeroを含んではならない。

解法

まず前半について、Nのうち頭x桁をaで割ったときの余りをR(x)とする。
Nの上からi桁目の値をN(i)とすると、R(x+1)=(R(x)*10+N(i))%aと計算できる。

逆にNのうち後ろy桁をbで割ったときの余りをS(y)とする。
するとS(y+1)=(S(y)+N(i)*(10^(y+1)))%bと計算できる。

両漸化式でR(x)、S(y)を列挙しておくことで、各分割位置に対して前半・後半がa,bで割り切れる位置を総当たりできるようになる。

なお以下の式では先にS(N-1)を求めてS(N-2)、S(N-3)…と逆に減らして行っている。

string S,T;
int A,B,L;
int p10[1000001];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>A>>B;
	L=S.size();
	
	ll v1=0,v2=0;
	p10[0]=1;
	T=S;
	FOR(i,L) S[i]-='0';
	FOR(i,L) p10[i+1]=p10[i]*10%B, v2=(v2+p10[i]*S[L-1-i])%B;
	
	FOR(i,L-1) {
		v1=(v1*10+S[i])%A;
		v2=(v2+B-p10[L-1-i]*S[i]%B)%B;
		if(v1==0 && v2==0 && S[i+1]!=0) {
			cout << "YES" <<endl;
			cout << T.substr(0,i+1) <<endl;
			cout << T.substr(i+1) <<endl;
			return;
		}
	}
	cout<<"NO"<<endl;
	
}

まとめ

ここらへんはまだ簡単。