Codeforces 394(#231 Div1) B. Very Beautiful Number

問題

p桁の数で、Leading zeroがなく、下一桁を一番上にもってくると元の数のx倍になるような数最小の数を求めよ。
そのような数がないときはImpossibleと答えよ。

制約条件

1≦p≦10^6
1≦x≦9

方針

元の数の1の位を全通り試す。
a[0] * xの1の位は、ずらした数の1の位である。これは元の数の10の位なので、
a[1] = a[0] * x % 10である。

これを繰り返していけば、a[p - 1]までが求まる。
あとはつじつまが合っているかと、leading zeroになってないかを見て、
最小の数を答えればいい。

ソースコード

int p, x, a[1000100];

int main(){
	cin >> p >> x;
	string ans(1, '9' + 1);
	for(int d = 1; d < 10; d++){
		int c = 0;
		a[0] = d;
		rep(i, p - 1){
			a[i + 1] = (a[i] * x + c) % 10;
			c = (a[i] * x + c) / 10;
		}
		if(a[p - 1] == 0 || a[p - 1] * x + c != d) continue;
		string s;
		rep(i, p) s += a[p - 1 - i] + '0';
		ans = min(ans, s);
	}
	cout << (isdigit(ans[0]) ? ans : "Impossible") << endl;
	return 0;
}