117 B Very Interesting Game

問題

三つの数a,b,modが与えられる。二人が次のようなゲームをする。

• 1人目がa以下の数s1を選ぶ。s1は9桁の数で、leading zeroがあっても良い。
• 2人目がb以下の数s2を選ぶ。s2は9桁の数で、leading zeroがあっても良い。
• 文字列s1+s2を数字として見たときにmodで割りきれれば1人目の勝ち、そうでなければ二人目の勝ち。

お互いが最善を尽くしたとき、どちらのプレイヤーが勝つか求めよ。
1人目のプレイヤーが勝つとき、1人目が最初に書くs1のうち辞書順で最小のものを求めよ。

制約条件

a,b≦10^9
mod≦10^7

方針

全探索。
aは辞書順最小のものを求めるので、mod以下のs1についてだけ考えれば良い。
s1が決まると、s2をmodで割った余りが一意に定まる。このうち最小のものだけ考えればいいので、
それがb以下であるかを見る。

それがb以下なら2人目が勝ってしまうので次のs1を見る。
bより大きいなら1人目が勝つので、そのときのs1を出力する。

ソースコード

int a,b,mod;
void run(){
  cin>>a>>b>>mod;
  rep(i,min(a+1,mod)){
    int rest=((-i*ll(1e9)%mod)+mod)%mod;
    if(rest>b){
      printf("1 %09d\n",i); return;
    }
  }
  puts("2");
}