Y箱

これもトーシェント関数の問題です。

普通に考えたら解けないのが分っているので、ちょっと考えます。





今回は、n/φ(n)を小さくするので、問題69で考えたことからすると、素因数の種類は少ないほうがいいということになります。
素因数を1つにするには、nは素数でなくてはならないのですが、nが素数のときのφ(n)は、n-1なので、これがpermutationになることはないでしょう。

ということで、素因数を2つとしてみます。少なくとも問題にある87109の素因数は2つなので、最悪、これが答になります。

さて、素因数が2つということは、

n=p1*p2

ということになります。 また、そのときのトーシェント関数の値は、

φ(n) = φ(p1)*φ(p2) = (p1-1)*(p2-1)

なので、掛けたときに10^7未満になる素数の組を作って、φ(n)とnがpermutationになるかどうか確認します。

20秒弱で解けましたけど、終了条件が分ればもっと速く解けるんじゃないかと思うんだけど、思いつかない。