AOJ1269 Sum of Different Primes

問題リンク Sum of Different Primes

• 概要

整数NをK個の異なる素数の和で表す方法は何通りあるか答えよ。3+5と5+3などは重複して数えてはならない。
N <= 1120
K <= 14

• 解法

メモ化再帰で解くことができます。
dp[i][j][k]: 整数iをj番目以降の素数をk個使って表す方法の個数
という部分問題に落とせます。1120以下の素数の数は187個なので、1120*187*14 = 3*10^6程度の計算量になります。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Sum of Different Primes
public class AOJ1269 {

	int N = 1120, num;
	int[] p;
	int[][][] dp;
	
	int get(int x, int index, int rest){
		if(rest==0){
			if(x==0)return dp[x][index][rest] = 1;
			else return dp[x][index][rest] = 0;
		}
		if(dp[x][index][rest]!=-1)return dp[x][index][rest];
		int res = 0;
		for(int i=index;i<num;i++){
			if(x<p[i])break;
			res += get(x-p[i], i+1, rest-1);
		}
		return dp[x][index][rest] = res;
	}
	
	void run(){
		num = 0;
		p = new int[187];
		boolean[] prime = new boolean[N+1];
		Arrays.fill(prime, true);
		prime[0]=prime[1]=false;
		for(int i=2;i<=N;i++)if(prime[i]){
			p[num++] = i;
			for(int j=i+i;j<=N;j+=i)prime[j]=false;
		}
		dp = new int[N+1][num+1][15];
		for(int i=0;i<=N;i++)for(int j=0;j<=num;j++)for(int k=0;k<=14;k++)dp[i][j][k]=-1;
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt(), k = sc.nextInt();
			if((n|k)==0)break;
			System.out.println(get(n, 0, k));
		}
	}
	
	public static void main(String[] args) {
		new AOJ1269().run();
	}
}