TopCoder SRM 760 : Div1 Medium CatAndMice

こっちは割とすんなり。
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でトーシェント関数がどうたらとかネタバレ見ちゃったしねぇ。