こっちは割とすんなり。
https://community.topcoder.com/stat?c=problem_statement&pm=15530
問題
(-N,-N)~(N,N)の矩形範囲における、原点以外の格子点を考える。
原点から任意の向きに半直線を伸ばすことを考える。
その際、上記格子点をちょうどC個通るような傾きは何通りか。
解法
N=Cの時は、明らかに0度から45度単位で8通り選べばよい。
以下、C<Nの場合を考える。
対象性から、第1象限のうちY座標がX座標より小さい範囲だけを考えることにしよう。
最後に8倍すればつじつまが合う。
仮に条件を満たす直線が(AC,BC)を通り、これが原点から近い順に見てちょうどC個目の格子点である条件を考えよう。
この直線は(A(C+1),B(C+1))も通るので、この直線が条件を満たすにはA(C+1)>Nでなければならない。
また、AとBが互いに素でない場合、(AC,BC)までにC*GCD(A,B)個交点ができてしまうのでやはり条件を満たさない。
こうなると、BはA未満の正整数のうちAと互いに素なものでなければならず、その個数はトーシェント関数で求められる。
よって、以下の手順を取ろう。
- まずNまでの全正整数についてトーシェント関数の値を求めておく。これはNの約数を逐一求めると間に合わないので、エラトステネスの篩の要領で行う。
- 条件を満たすX座標を総当たりする。
- Bの候補として、φ(A)個あるのでその和を求める。
- 最後に8倍する
int P[5050505]; int T[5050505]; class CatAndMice { public: long long countDirections(int N, int C) { if(N==C) return 8; int i,j; FOR(i,5000001) { P[i]=1; T[i]=i; } for(i=2;i<=5000000;i++) if(P[i]) { for(j=i;j<=5000000;j+=i) { P[j]=0; T[j]=T[j]/i*(i-1); } } ll ret=0; for(int x=C;x<=N;x+=C) { int a=x/C; if(1LL*a*(C+1)>N) { ret+=T[a]; } } return ret*8; } }
まとめ
まぁ先にTwitterでトーシェント関数がどうたらとかネタバレ見ちゃったしねぇ。