PKU 2897 Dramatic Multiplications

問題

ある数がn-dramaticであるとは、
n倍したときに10進法での最下位の数字が、最上位に巡回シフトされるような数を言う。

最下位がkであるようなn-dramaticな数のうち最小であるものを求めよ。

制約条件

n, k≦9

方針

(10 n - 1) x = (10^m k - n k)みたいな感じに表せることが必要十分。
なのでmを決め打ちして全探索。

多倍長が必要。

ソースコード

ll n, k;

int main(){
	
	int cs;
	cin >> cs;
	while(cs--){
		cin >> n >> k;
		
		BigNum ten = ONE, prev = ZERO;
		if(n == 1){
			cout << k << endl;
			goto END;
		}
		
		for(int i = 0; i < 300; i++, prev = ten, ten = ten * 10){
		
			if(ten * k < n * k) continue;
			if((ten * k - n * k) % (10 * n - 1)) continue;
			
			BigNum x = (ten * k - n * k) / (10 * n - 1);
			if(x < prev || x >= ten) continue;
			cout << (x * 10 + k) << endl;
			goto END;
		}
		cout << 0 << endl;
		END:;
	}
	return 0;
}