XとNが互いに素ならX,2X,...,NX(modN) は全て異なる値になります。
したがって、XとNが互いに素のとき全ての寿司を食べることができます。
ただし、Xが最大で1010になることから、全てのXを順番に調べると無限に時間がかかってしまいます。
そこでNを素因数分解し、オイラーのφ関数を使って計算することで計算量を減らします。
例えば N=12=2×2×3 なら互いに素な整数の個数は 12(1−21)(1−31) で計算できます。
この計算には2の倍数でない数が全体の21あり、その中で更に3の倍数でない数が32ある、という有名な説明があります。
素因数分解がボトルネックとなり全体計算量は O(N) となります。