解答
数を多項式としてみなすことを考えましょう。
具体的には、ある数を二進数表記をしたとき,ビット目が立っている時にを要素にもつような 全ての係数がの多項式を対応させます。
たとえば、 ですのでとなります。
加えていくつかの定義をします。
はじめに、つの整数係数多項式が全ての係数において偶奇が等しいとき これらは「互いに法をとして合同である」とし、「」とかくことにします。
たとえば、
は互いに法をとして合同でです。
つめに、多項式に対して、以下を満たす整数係数多項式が存在する場合、「はで割り切れる/はの因数である」ということにします。
・
たとえば、
としたとき
ですので「はで割り切れる/はの因数」です。
ここで、を上記の規則に従って多項式に対応させた結果得られる多項式をとします。
つめに、整数係数の多項式の集合をとし、に属する多項式のうち、以下を満たすが存在する多項式の集合をとします。
明らかに、題意の操作を繰り返して得られる数を多項式に変換した時、それらはに含まれるものであることがわかります。
そして、全てのを割り切る多項式のうち、全ての係数がになるものが存在します。
これをとし、これが以外に存在しないことが必要十分条件でもあります。(が条件を満たすことは明らか。）
このようなを求めるには、多項式に対して通常の整数と同様にの互助法的な考え方をもちいて再帰的に計算を行えば良いです。
適切に実装を行えば、時間計算量の回答を得ることができます。