project euler 72
問題
nとdを正の整数とし、n
考え方
分子がn(1〜N-1)の時に、nの素因数で割り切れないdの個数を求めれば、分子がnの既約分数の個数を求められる。
N以下の整数の、素因数リストの少なくとも1つで割り切れるものの個数は、包除原理で求められるので、各nについて求めて足し合わせればよい。
(包除原理の部分は、蟻本の「数え上げ 包除原理」のところを参照)
nとdを正の整数とし、n
分子がn(1〜N-1)の時に、nの素因数で割り切れないdの個数を求めれば、分子がnの既約分数の個数を求められる。
N以下の整数の、素因数リストの少なくとも1つで割り切れるものの個数は、包除原理で求められるので、各nについて求めて足し合わせればよい。
(包除原理の部分は、蟻本の「数え上げ 包除原理」のところを参照)