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; }