project euler 71
問題
既約分数n/d(ただし、n>d)を考える。
d<=8の時、3/7より小さいもので最大の既約分数は2/5になる。
d<=1000000の時、3/7より小さいもので、最大の既約分数の分子の数を答える。
考え方
dが決まった時に、nの値は、n<3*d/7を満たす最大の整数である。
これはO(1)で求められるので、dについて回して、3/7より小さいもので最大となるものを答える。
誤差があるかもしれないので、できるだけ整数で扱う。
a/b
既約分数n/d(ただし、n>d)を考える。
d<=8の時、3/7より小さいもので最大の既約分数は2/5になる。
d<=1000000の時、3/7より小さいもので、最大の既約分数の分子の数を答える。
dが決まった時に、nの値は、n<3*d/7を満たす最大の整数である。
これはO(1)で求められるので、dについて回して、3/7より小さいもので最大となるものを答える。
誤差があるかもしれないので、できるだけ整数で扱う。
a/b