解説
結論から書くと,bit全探索 + 中国剰余定理が想定です.
目覚まし時計が同時に鳴る周期が短ければシミュレーションすることができますが,本問題の制約では周期が109を超えることがあり厳しいです.
そこでNが小さいことに注目します.
全ての目覚まし時計の組み合わせについて調べ,「音量の合計がK以上」となるような目覚まし時計の組が同時に鳴る最小の時刻が求める答えです.
いくつかの目覚まし時計が同時に鳴る最小の時刻は,(存在するならば)拡張ユークリッドの互除法を繰り返し適用することで求めることができます.(実装上はACLのcrtを使うのが楽です).
各組み合わせの最小の時刻においては,注目している目覚まし時計が全て鳴り始めている必要があることに注意してください.
より定式的に,目覚まし時計の部分集合をSとします.
中国剰余定理よりt≡Ai(modBi),∀i∈S
の解が存在するならば,
t≡z(mod lcmi∈S(Bi))と書き表せます.
i∈S∑Ci≥Kが成り立つすべてのSについての,t≥maxi∈SAiかつt≡z(mod lcmi∈S(Bi))をみたす最小のtが求める解です.
計算量は,O(2NNloglcm(Bi))です.
※ lcm(1,2,…,30)=2329089562800<1018より,64bit整数の範囲内で拡張ユークリッドの互除法が正しく動きます.