JOI2006模擬試験1 問題5@C++(未完)(19)

boysの大きい方からデクリメントして素数判定するアルゴリズムなんだけど、入力5の残酷さが半端じゃない。

  • 値のレンジが100000000000000000000くらいまであるのでunsigned long longでも足りないのでboys,girlsに分割して素数判定するはめに。
  • 素数判定もやけに時間がかかる。既知の素数はキャッシュしたが、それでも重い。
  • というわけで入力5を解くのに数十分かかった><

だが、悔しいので解答は見ない

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

using namespace std;

typedef unsigned long long ullong;

const ullong digits[] = {
	1,
	10,
	100,
	1000,
	10000,
	100000,
	1000000,
	10000000,
	100000000,
	1000000000,
	10000000000LL,
	100000000000LL};
const bool first_allowed[] = {false, true, false, true, false, false, false, true, false, true};
int n,c;
ullong boys_mul;
ullong c_mul;
vector<ullong> pnums;
ullong pnums_max=0;

void addpnums()
{
	vector<bool> nums(1048576,true);
	ullong base=pnums_max;
	if(base<2)base=2;
	ullong ceil=base+nums.size();
	for(vector<ullong>::iterator ii=pnums.begin();ii!=pnums.end();ii++) {
		ullong i=*ii;
		ullong start=(base/i)*i;
		for(ullong j=start;j<ceil;j+=i) {
			if(j<base)continue;
			nums[j-base]=false;
		}
	}
	for(ullong i=base;i<ceil;i++) {
		if(nums[i-base]) {
			pnums.push_back(i);
			ullong start=(base/i)*i;
			for(ullong j=start;j<ceil;j+=i) {
				if(j<base)continue;
				nums[j-base]=false;
			}
		}
	}
	pnums_max=ceil;
}

void println_bcg(ullong boys, ullong girls)
{
	for(int i=0;i<n;i++) {
		printf("%c",(char)(((boys/digits[n-1-i])%10)+'0'));
	}
	if(c>=0) {
		printf("%c",c+'0');
	}
	for(int i=0;i<n;i++) {
		printf("%c",(char)(((girls/digits[n-1-i])%10)+'0'));
	}
	printf("\n");
}

bool search(ullong boys, ullong girls, int depth)
{
	if(depth==n) {
		//ullong current=boys*boys_mul + c*c_mul + girls;
		//for(ullong i=2;i<boys_mul;i++) {
		for(vector<ullong>::iterator ii=pnums.begin();ii!=pnums.end() && *ii<boys_mul;++ii) {
			ullong i=*ii;
			//if(current%i==0 && current!=i) {
			if(
				(
					boys*(boys_mul%i) + 
					c*(c_mul%i) + 
					girls
				)%i==0
			) {
				return false;
			}
			while(ii+1==pnums.end()) {
				addpnums();
			}
		}
		//printf("%llu\n", boys*boys_mul + c*c_mul + girls);
		//printf("%llu\n",current);
		println_bcg(boys,girls);
		return true;
	}
	for(int i=9; i>=0; i--) {
		if(depth==0 && !first_allowed[i]) {
			continue;
		}
		if(search(boys + i*digits[n-1-depth], girls + i*digits[depth], depth+1)) return true;
	}
	return false;
}

int main(int argc, char* argv[])
{
	addpnums();
	scanf("%d %d\n",&n,&c);
	boys_mul = digits[(c < 0) ? n : n+1];
	c_mul = (c < 0) ? 0 : digits[n];
	if(!search(0,0,0)) {
		println_bcg(digits[n]-1,digits[n]-1);
	}
	return 0;
}