結果

問題 No.719 Coprime
コンテスト
ユーザー startcpp
提出日時 2018-07-17 19:25:01
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 4,682 bytes
コンパイル時間 664 ms
コンパイル使用メモリ 70,064 KB
実行使用メモリ 14,336 KB
最終ジャッジ日時 2024-11-26 07:45:47
合計ジャッジ時間 170,763 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 20 TLE * 41
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int dfs(int, int, long long int)’:
main.cpp:66:13: warning: control reaches end of non-void function [-Wreturn-type]
   66 |         ret = max(ret, res);
      |         ~~~~^~~~~~~~~~~~~~~

ソースコード

diff # 

//嘘解法。以下のパターンを試し、最もよかったものを取る。
//1. N ≦ 45なら、全探索
//2. N,N-1,…,2の順で見ていき取れるなら取る。
//3. 2,3,…,Nの順で見ていき取れるなら取る。
//4. 最大素因数がp_iの数のうち取ることができる最も大きいものを取る、をi=k,…,2,1の順でおこなう。
//kはN以下の素数の個数 。p_iはi番目に小さい素数。(p_1 = 2)
//5. 最大素因数がp_iの数のうち取ることができる最も大きいものを取る、をi=1,2,3…の順でおこなう。
//6. 素数だけを取る。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

//0. 最大素因数の表を作る
vector<int> primes;
vector<vector<int>> numbers;

void setPrimes(int n) {
	int i, j;
	vector<bool> isprime(n + 1);
	
	isprime[0] = isprime[1] = false;
	for (i = 2; i <= n; i++) isprime[i] = true;
	
	for (i = 2; i <= n; i++) {
		if (isprime[i]) {
			for (j = i * 2; j <= n; j += i) {
				isprime[j] = false;
			}
		}
	}
	
	for (i = 2; i <= n; i++) if(isprime[i]) primes.push_back(i);
	
	numbers.resize(primes.size());
	for (i = 2; i <= n; i++) {
		for (j = primes.size() - 1; j >= 0; j--) {
			if (i % primes[j] == 0) {
				numbers[j].push_back(i);
				break;
			}
		}
	}
}

//1. 全探索(2,3,…,Nの順で取る・取らないを決める）
int dfs(int val, int n, long long taked) {
	if (val > n) return 0;
	
	int i, res, ret = 0;
	for (i = 2; i < val; i++) {
		if ((taked >> i) % 2 == 0) continue;
		if (gcd(i, val) != 1) break;
	}
	if (i == val) {	//取る
		res = val + dfs(val + 1, n, taked + (1LL << val));
		ret = max(ret, res);
	}
	res = dfs(val + 1, n, taked);
	ret = max(ret, res);
}

//2. N,N-1,…,2の順で見ていき、取れるなら取る
int greedy_bigTake(int n) {
	int i, j;
	vector<bool> taked(n + 1, false);
	int ret = 0;
	
	for (i = n; i >= 2; i--) {
		for (j = i + 1; j <= n; j++) {
			if (taked[j] && gcd(j, i) != 1) break;
		}
		if (j > n) {	//iを取れる
			taked[i] = true;
			ret += i;
		}
	}
	return ret;
}

//3. 2,3,…,Nの順で見ていき、取れるなら取る
int greedy_smallTake(int n) {
	int i, j;
	vector<bool> taked(n + 1, false);
	int ret = 0;
	
	for (i = 2; i <= n; i++) {
		for (j = 2; j < i; j++) {
			if (taked[j] && gcd(j, i) != 1) break;
		}
		if (j >= i) {	//iを取れる
			taked[i] = true;
			ret += i;
		}
	}
	return ret;
}

//4. 最大素因数がp_iの数のうち取ることができる最も大きいものを取る、をi=k,…,2,1の順でおこなう。
//kはN以下の素数の個数 。p_iはi番目に小さい素数。(p_1 = 2)
int greedy_bigNumbers(int n) {
	int i, j, k;
	vector<int> taked;
	int ret = 0;
	
	for (i = numbers.size() - 1; i >= 0; i--) {
		for (j = numbers[i].size() - 1; j >= 0; j--) {
			int val = numbers[i][j];
			for (k = 0; k < taked.size(); k++) {
				if (gcd(val, taked[k]) != 1) break;
			}
			if (k == taked.size()) {
				taked.push_back(val);
				ret += val;
			}
		}
	}
	return ret;
}

//5. 最大素因数がp_iの数のうち取ることができる最も大きいものを取る、をi=1,2,3…の順でおこなう。
int greedy_smallNumbers(int n) {
	int i, j, k;
	vector<int> taked;
	int ret = 0;
	
	for (i = 0; i < numbers.size(); i++) {
		for (j = numbers[i].size() - 1; j >= 0; j--) {
			int val = numbers[i][j];
			for (k = 0; k < taked.size(); k++) {
				if (gcd(val, taked[k]) != 1) break;
			}
			if (k == taked.size()) {
				taked.push_back(val);
				ret += val;
			}
		}
	}
	return ret;
}

//6. 素数だけを取る。(primes…n以下の素数の集合）
int greedy_primeTake(int n) {
	int i;
	int ret = 0;
	for (i = 0; i < primes.size(); i++) ret += primes[i];
	return ret;
}

signed main() {
	bool debug_mode = false;
	int n;
	cin >> n;
	
	setPrimes(n);
	
	int ans = 0, res;
	
	if (n <= 45) {
		res = dfs(2, n, 0);
		if (debug_mode) cout << "score[dfs] = " << res << endl;
		ans = max(ans, res);
	}
	
	res = greedy_bigTake(n);
	if (debug_mode) cout << "score[greedy_bigTake] = " << res << endl;
	ans = max(ans, res);
	
	res = greedy_smallTake(n);
	if (debug_mode) cout << "score[greedy_smallTake] = " << res << endl;
	ans = max(ans, res);
	
	res = greedy_bigNumbers(n);
	if (debug_mode) cout << "score[greedy_bigNumbers] = " << res << endl;
	ans = max(ans, res);
	
	res = greedy_smallNumbers(n);
	if (debug_mode) cout << "score[greedy_smallNumbers] = " << res << endl;
	ans = max(ans, res);
	
	res = greedy_primeTake(n);
	if (debug_mode) cout << "score[greedy_primeTake] = " << res << endl;
	ans = max(ans, res);
	
	cout << ans << endl;
	return 0;
}
0