AGC028 A - Two Abbreviations
解法
long longの制約になっているかどうかしっかり確認しましょう(n回目)
まず、Lの最小値としてありうるのは、NとMの最公倍数になります。
よって、L全体としてありうるのは、Lの倍数になります。
ですが、実はLのp倍の長さの文字列がこの問題の条件を満たすとき、常に長さLでも条件を満たします。
(L×p)/Nをn、(L×p)/Mをmとします。
文字列SとTが、文字列X上で被る場所を探ります。
nとmの最小公倍数をQとすると、
L上でQ×q+1文字目(qは任意です)
の文字になります。これは、S、T上でいうと
SはQ×q/n+1文字目
TはQ×q/m+1文字目になります。
これは、実はpが1であろうとなんであろうと変わりがありません。
よって、文字列の長さがLであるときに、問題の条件を満たすかどうかを調べるだけで答えがわかるようになっています。
被る部分だけを調べるので、先ほどの式を利用してその部分だけ調べれば、答えが求まります。
