SRM 365 300pt: PointsOnCircle

TopCoder

問題概要

原点中心半径r(<2*10^9)の円がある。円周上にある格子点の数を求める問題。

考えたこと

  • 何か公式が与えられてるけどそれ使った解法がよく分からない。
  • とりあえず数列辞典に投げてみよう。
  • あった。色々調べたら、rの素因数で、4で割って1余るものの指数をa[i]とすると4*Π(1+2*a[i])が答えになるらしい。
  • 後は素因数分解するだけ。
#include <stdio.h>
#include <vector>
#include <cstring>

using namespace std;

typedef long long int64;

const int MAX_SIZE = 1<<18;
bool isPrime[MAX_SIZE];

void seive(){
	memset(isPrime, -1, sizeof(isPrime));
	bool *ps = isPrime;
	ps[0] = ps[1] = false;
	for(int i=2; i*i<MAX_SIZE; i++)if(ps[i]){
		for(int j=i<<1; j<MAX_SIZE; j+=i){
			ps[j] = false;
		}
	}
}

struct PointsOnCircle {

	int64 count(int64 r){
		seive();
		return func(r);
	}

	int64 func(int64 n){

		vector<int> ones; //4で割って1余る素因数の指数
		for(int i=2; i*i<=n; i++)if(isPrime[i] && n%i==0){
			int tmp = 0;
			while(n%i==0){
				n /= i;
				tmp++;
			}

			if(i%4==1){
				ones.push_back(tmp);
			}
		}

		if(n != 1 && n%4==1){
			ones.push_back(1);
		}

		//4で割って1余る素数のべきが大事
		int64 ret = 4;
		for(int i=0; i<(int)ones.size(); i++){
			ret *= (1 + 2*ones[i]);
		}

		return ret;
	}

};

バグを出さない工夫