結果

問題 No.1006 Share an Integer
コンテスト
ユーザー 東前頭十一枚目
提出日時 2020-03-06 22:35:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,009 bytes
コンパイル時間 1,617 ms
コンパイル使用メモリ 170,904 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2024-10-14 08:55:43
合計ジャッジ時間 21,883 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 8 WA * 7 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

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