//REの出るコード2 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Yukicoder { class Coprime { static int[,] dp = new int[500, 1 << 17]; public static void Main() { int n; n = int.Parse(Console.ReadLine().ToString()); List primes = get_primes(n); List> numbers = get_numbers(primes, n); //numbers[i] = 最大素因数がprimes[i]である数の集合 for (int i = 0; i < 500; i++) { for (int j = 0; j < (1 << 17); j++) { dp[i, j] = -1; //undefined } } int answer = dfs(n, primes, numbers, 0, 0); Console.WriteLine(answer); } //n…(カードに書かれた)値の上限 //primes[i]…i(>=0)番目に小さい素数 //numbers[i]…最大素因数がprimes[i]の数の集合 //prime_id…最大素因数がprime_id以上の数を今から選ぶ //usedの下位iビット目…primes[i]で割り切れる数を既に取ったなら1, 取ってないなら0 //返り値:これから選ぶ値の和の最大値 public static int dfs(int n, List primes, List> numbers, int prime_id, int used) { if (prime_id >= primes.Count()) { return 0; } if (dp[prime_id, used] >= 0) { return dp[prime_id, used]; } int i, j; int max_score = 0; max_score = dfs(n, primes, numbers, prime_id + 1, used); for (i = 0; i < numbers[prime_id].Count(); i++) { bool can_take = true; int take_num = numbers[prime_id][i]; for (j = 0; j < prime_id; j++) { if (take_num % primes[j] == 0 && (used >> j) % 2 == 1) { can_take = false; break; } } if (can_take) { int new_used = used; for (j = 0; j <= prime_id; j++) { if (take_num % primes[j] == 0) { new_used |= (1 << j); } } max_score = max(max_score, take_num + dfs(n, primes, numbers, prime_id + 1, new_used)); } } return (dp[prime_id, used] = max_score); } public static List get_primes(int max_value) { int i, j; List primes = new List(); //空の動的配列を作って, primesというあだ名を付ける。 for (i = 2; i <= max_value; i++) { for (j = 2; j * j <= i; j++) { if (i % j == 0) { break; } } if (j * j > i) { primes.Add(i); } } return primes; //素数テーブルを返します } public static List> get_numbers(List primes, int max_value) { int i, j; List> numbers = new List>(primes.Count()); //2次元の動的配列を作って, numbersというあだ名をつける。引数は最大容量(capacity)であり, 実際に使えるサイズとは異なるので注意。 for (i = 0; i < primes.Count(); i++) { numbers.Add(new List()); //Listの指す「実物の配列」を作る, で, そのアドレスをnumbersに追加していく。 } for (i = 2; i <= max_value; i++) { for (j = primes.Count() - 1; j >= 0; j--) { if (i % primes[j] == 0) { numbers[j].Add(i); break; } } } return numbers; } public static int max(int a, int b) { if (a > b) { return a; } return b; } } }