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