問題 nとdを正の整数とし、n 考え方 分子がn(1〜N-1)の時に、nの素因数で割り切れないdの個数を求めれば、分子がnの既約分数の個数を求められる。 N以下の整数の、素因数リストの少なくとも1つで割り切れるものの個数は、包除原理で求められるので、各nにつ…

問題 オイラーのφ関数についてφ(n)の各桁の数を並び替えたものがnになるものを考える。 1 考え方 実際に試してみる。

問題 三角形の各頂点の座標が与えられる。その三角形が原点を内部に含むかどうかを判定する。 考え方 3点の回転方向を求める関数を用意する。 三角形の頂点x,y,zについて、 xy,yz,zxの線分上に原点がある x->y->0, y->z->0, z->x->0の回転方向がすべて同じな…

問題 正N角形の各頂点だけが配置されている。 ある頂点リストpoints(M個、N 考え方 bitDP。蟻本の「3-4 動的計画法を極める！」と同じような感じで、dp[辿った頂点集合][今いる頂点]で2重ループで書ける。今の辿った頂点集合stと今いる頂点vについて、まだた…