JOI2006模擬試験2 問題4@C++(30)

s=2xy+x+yを(2s+1)=(2x+1)(2y+1)つまり奇数の積に変形できるので、一般の素数判定を利用できる。

面積sはintの範囲内だがts=s*2+1はintではなくuintを使う必要があるというところでミスった。orzorz

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

typedef unsigned int uint;

vector<uint> pnums;
void mkpnums()
{
	vector<bool> nums(65536,true);
	for(uint i=2;i<nums.size();i++) {
		if(nums[i]) {
			pnums.push_back(i);
			for(uint j=i*2;j<nums.size();j+=i) {
				nums[j]=false;
			}
		}
	}
}

int main(int argc,char* argv[])
{
	mkpnums();
	uint n;
	scanf("%d\n",&n);
	uint count=0;
	for(uint i=0;i<n;i++) {
		uint s;
		scanf("%d\n",&s);
		uint ts=s*2+1;
		count++;
		for(vector<uint>::iterator j=pnums.begin();j!=pnums.end();++j) {
			if(ts%*j==0 && ts!=*j) {
				count--;
				break;
			}
		}
	}
	printf("%d\n",count);
	return 0;
}