...と、流石にこの時点で終わることはできません。$n$の値の範囲を見るに、ループ繰り返し回数が億行ってしまう可能性もあるわけで、とても処理時間的にが間に合う見込みがありません。$n$が大きくなっても耐えられるように、GCDの値毎に分類して総和を求めると考えてみましょう。例題にあった$F(9,12)=22$であれば、次のようにまとめることができます。6$ただ、まとめたとは言え、和を計算する部分は$(1+5+7)$のように歯抜けになってしまっていますから、これでは一括で計算というわけには行きません。巧く対処を考える必要があります。ここで単純な例、ということで素因数が1種類の$k=3^2=9$で考えてみます。各自然数$m$は次のように分類できるはずです。$\frac{m}{9}$を加算$k$の方で上限ができていますから、27の倍数,81の倍数,...と延々考える必要はなく、この3パターンのみです。ここで、歯抜けを解消するために次のように変換してみます。$\frac{m}{9}=m-(3-1)\times(\frac{m}{3}+\frac{m}{9})$を加算つまり、下の方の分類になったとしても、それより上の分類で現れる項を保持した形に変換しているわけで、これで歯抜けを解消しようという目論見です。これで実際、$F(100,9)$は次のように歯抜けの無い総和で計算できます。増えたとしても同じように順々に計算できるはずです。これで大分見通しが立ちました。最後に残った問題は$k$が複数の素因数を持ちうるということです。...なんですが、まあそんな時には再帰でなんとかなります。