kmjp's blog

競技プログラミング参加記です

TopCoder SRM 734 Div1 Easy TheRoundCityDiv1

ネタ切れを疑うような問題。
https://community.topcoder.com/stat?c=problem_statement&pm=14897

問題

整数Rが与えられる。
2次元座標系において、以下の条件を満たす原点以外の格子点の数を求めよ。

  • 原点との距離がR以下である。
  • 原点とその点を結ぶ線分に、他の点が含まれない。

解法

X軸およびY軸上で該当する点は(1,0)(-1,0)(0,1)(0,-1)の4通りで固定。
あとは第1象限における条件を満たす頂点数を考え、それを4倍しよう。

X座標xを総当たりすることにする。前者の条件だけ考えると、候補となるy座標は1≦y≦sqrt(R*R-x*x)である。
あとここから後者の条件に合致しないものを取り除くことになるが、要はxと互いに素なyの数を求める問題となる。
これはxを素因数分解しておけば包除原理の要領で求めることができる。

const int prime_max = 1100000;
int NP,prime[100000],divp[prime_max];
map<int,int> M;

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime[NP++]=i;
		divp[i]=i;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

class TheRoundCityDiv1 {
	public:
	long long find(int r) {
		
		cprime();
		
		ll ret=1;
		for(ll x=1;x<=r;x++) {
			ll y=0,i;
			for(i=20;i>=0;i--) if((x*x+(y+(1<<i))*(y+(1<<i)))<=(ll)r*r) y+=1<<i;
			vector<int> S;
			int z=x;
			while(z>1) S.push_back(divp[z]), z/=divp[z];
			sort(ALL(S));
			S.erase(unique(ALL(S)),S.end());
			for(int mask=0;mask<(1<<S.size());mask++) {
				int p=1,si=1;
				FOR(i,S.size()) if(mask&(1<<i)) p*=S[i], si=-si;
				ret+=(y/p)*si;
				
			}
			
			
		}
		return ret*4;
	}
}

まとめ

どこかで出てそう。