AtCoder Beginner Contest 304F - Shift Table
メモ
Nの約数M(N < M)について
青木君のシフトを周期Mで決めた時に、すべての日程でどちらかが居ないといけない。
そのような青木君のシフトを数え上げろという問題
複数の操作列(M, 長さMのシフト)について、同じシフトが重複してしまう事があるのが難しい点
こういう時はgreedyからの帰着(数え上げpdf)に沿って、判定問題を考えるかという気持ちになる
しかし今回はそんなに感触が良くない。(操作列で作るっていうような問題設定でもないからかも) あと、シフト列が作れるかの判定にgreedyに考えるとか関係ないので
判定問題を考えたくならないような問題の場合は、greedyからの帰着をあまり考えない方が良いかもと思っておこう
重複を避けるために任意のシフト列について、それを構成しうる最小のMにそれを持たせて、それを数え上げる
なぜなら、周期x(xはNの約数)で作れる時、周期 k * x(k * x はNの約数)でも作れるため
後は約数包除で出来る
