#439832 (C++14) No.1006 Share an Integer

• 問題: No.1006 Share an Integer
• ユーザー: 東前頭十一枚目
• 提出日時: 2020-03-06 22:35:47
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 1,009 bytes
• コンパイル時間: 1,758 ms
• コンパイル使用メモリ: 169,016 KB
• 実行使用メモリ: 11,584 KB
• 最終ジャッジ日時: 2024-04-22 09:42:12
• 合計ジャッジ時間: 22,809 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	1,075 ms; 7,808 KB
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	AC	1,966 ms; 10,588 KB
testcase_16	AC	749 ms; 7,040 KB
testcase_17	AC	1,131 ms; 8,064 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	TLE	-
testcase_21	TLE	-

ソースコード

#include <bits/stdc++.h>
using namespace std;

vector<int> SieveOfEratosthenes(int n) {
	n++;
	vector<bool> list(n, true);
	for(int i = 2; i * i < n; ++i) {
		if(list[i]){
			for(int j = 2; i * j < n; ++j) {
				list[i * j] = false;
			}
		}
	}
	vector<int> ret;
	for(int i = 2; i < n; ++i) {
		if(list[i]) ret.push_back(i);
	}
	return ret;
}


int f[2000010];
int main() {
	int x; cin >> x;
	int m;
	for(m = 1; m * m <= x; ++m);
	vector<int> v = SieveOfEratosthenes(m);
	int vn = v.size();
	for(int i = 1; i <= x; ++i) {
		int tmp = i;
		int cnt[vn] = {};
		for(int j = 0; j < vn; ++j) {
			while(tmp > 0 and tmp % v[j] == 0) {
				tmp /= v[j];
				++cnt[j];
			}
		}
		int d = 1;
		for(int j = 0; j < vn; ++j) {
			d *= (cnt[j] + 1);
		}
		f[i] = i - d;
	}
	int diff = 1e9;
	for(int i = 1; i <= x; ++i) {
		if(abs(f[i] - f[x - i]) < diff) {
			diff = abs(f[i] - f[x - i]);
		}
	}
	for(int i = 1; i <= x; ++i) {
		if(abs(f[i] - f[x - i]) == diff) {
			cout << i << " " << x - i << '\n';
		}
	}
	return 0;
}