Xmas Contest 2011 A : input

問題概要

正整数をいくつかとってきて、sum A[i] <= 150, prod A[i] = X (mod 10^9+9)となるようなものを出力する問題。ない場合はその旨出力する。

解法

A[i]は合成数より素数をとった方が和を減らせるので得。なのでそのような素数の組み合わせについて全探索する。あまりに愚直な探索だとTLEするので、和が150を越えないことを利用した枝刈りくらいは必要。また、X=1のとき空の数列を返さないよう注意する。

acceptされたコード

#include <cstdio>
#include <vector>
#include <numeric>
#include <cstring>
using namespace std;

typedef  long long int64;

const int64 MOD = (int)1e9 + 9;
const int MAX_N = 150;

const int MAX_SIZE = 300;
bool isPrime[MAX_SIZE];
vector<int> primes;
int path[MAX_N];
char col[26*26][10];

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


int X, L;

void init(){
	scanf("%d", &X);
	seive();
	for(int i=2; i<=MAX_N; i++){
		if(isPrime[i]){
			primes.push_back(i);
		}
	}

	L = primes.size();

	for(int i=0; i<26; i++){
		for(int j=0; j<26; j++){
			col[i*26 + j][0] = i + 'a';
			col[i*26 + j][1] = j + 'a';
		}
	}
}

void prn(){
	int ans = 0;
	for(int i=0; i<L; i++){
		ans += primes[i] * path[i];
	}
	printf("%d\n", ans);

	for(int i=0, p=0; i<L; i++)if(path[i] > 0){
		for(int k=0; k<path[i]; k++){
			for(int j=0; j<primes[i]; j++){
				puts(col[p]);
			}
			p++;
		}
	}
}

bool search(int idx, int64 cur, int sum){

	if(cur == X){
		prn();
		return true;
	}

	if(idx == L){
		return false;
	}

	int64 q = 1;
	if(sum + primes[idx] > MAX_N){
		return false;
	}
	for(int i=0, p=0; sum + p <= MAX_N; p+=primes[idx], i++){
		path[idx] = i;
		if(search(idx+1, cur*q%MOD, sum + p)){
			return true;
		}
		q = q * primes[idx] % MOD;
	}
	path[idx] = 0;

	return false;
}

void solve(){
	if(X==1){
		puts("1");
		puts("a");
	}
	else if(!search(0, 1, 0)){
		puts("NO");
	}
}

int main(){
	init();
	solve();

	return 0;
}