既約分数 \(p/q\) (\(q\le2\times10^9\)) であって \(f(p/q)=0\) を満たすものを見つける方針は https://atcoder.jp/contests/abc324/editorial/7412 と同じです。

Stern–Brocot tree で探索する方法もあります。 解説および類題については下記に載っています。

https://rsk0315.hatenablog.com/entry/2023/04/17/022705

計算量は、答えを \(p/q\) として \(O((N+M)\log(q))\) 時間です。こちらの解説 の反復回数と比べるとやや劣ってはいますが、十分に高速で汎用的な方法なので、覚えておいてもよいでしょう。