競技プログラミング用 知識集積所
ARC200B - LCM
最終更新：
sport_programming
-
view
問題
必要知識
簡単な内容は省略
- 特になし
考え方
m桁の数をn桁の数をかけると、m+n桁もしくはm+n-1桁になる。
最小公倍数は積以下にしかならないので、a1+a2<a3の場合は不可能であるとすぐにわかる。
また、最小公倍数は元の数以上になるので、a1>a3やa2>a3の場合も明らかに不可能。
最小公倍数は積以下にしかならないので、a1+a2<a3の場合は不可能であるとすぐにわかる。
また、最小公倍数は元の数以上になるので、a1>a3やa2>a3の場合も明らかに不可能。
さて、残りの場合を考える。
まず、a1+a2=a3である場合。
これは、x1とx2を、最大公約数が1であるような最高位が4以上である数にしておけばよい。
最大公約数を1にするには、何かうまい法則を用いてもよいし、素数表からその桁数の大きな素数2つを探してコード内に入れておいてもよい。
これは、x1とx2を、最大公約数が1であるような最高位が4以上である数にしておけばよい。
最大公約数を1にするには、何かうまい法則を用いてもよいし、素数表からその桁数の大きな素数2つを探してコード内に入れておいてもよい。
次に、a1+a2=a3-1である場合。
これは、(a1-1)+(a2-1)=(a3-1)と変形できることから、全て1小さい桁数で上の場合と同じ方法を用いておき、その後全部を10倍すればよい。
ただし、a1やa2が1であった場合だけはこの方法が使えない。
この場合は、a2=a3もしくはa1=a3が成り立っているので、全部10の累乗にしておくだけでよい。
これは、(a1-1)+(a2-1)=(a3-1)と変形できることから、全て1小さい桁数で上の場合と同じ方法を用いておき、その後全部を10倍すればよい。
ただし、a1やa2が1であった場合だけはこの方法が使えない。
この場合は、a2=a3もしくはa1=a3が成り立っているので、全部10の累乗にしておくだけでよい。
さらに、a1+a2=a3-2である場合。
これは、(a1-2)+(a2-2)=(a3-2)と変形できることから、全て2小さい桁数で上の場合と同じ方法を用いておき、その後全部を100倍すればよい。
ただし、a1やa2が2であった場合だけはこの方法が使えない。
この場合は、a2=a3もしくはa1=a3が成り立っているので、全部10の累乗にしておくだけでよい。
これは、(a1-2)+(a2-2)=(a3-2)と変形できることから、全て2小さい桁数で上の場合と同じ方法を用いておき、その後全部を100倍すればよい。
ただし、a1やa2が2であった場合だけはこの方法が使えない。
この場合は、a2=a3もしくはa1=a3が成り立っているので、全部10の累乗にしておくだけでよい。
以下、同様に、a1+a2=a3-dである場合は、全部d小さい数で上の方法と同様に解けばよい。
