結果
問題 | No.1006 Share an Integer |
ユーザー |
|
提出日時 | 2020-03-06 21:37:23 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 1,051 bytes |
コンパイル時間 | 1,006 ms |
コンパイル使用メモリ | 139,008 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-11-30 16:40:29 |
合計ジャッジ時間 | 3,600 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <iostream> #include <cmath> #include <algorithm> #include <vector> constexpr int X = 2000000; std::vector<int> pcnt(X + 1, 1); void init() { for (int p = 2; p <= X; ++p) { if (pcnt[p] > 1) continue; for (int q = p; q <= X; q += p) { int cnt = 0, x = q; while (x % p == 0) { x /= p; ++cnt; } pcnt[q] *= cnt + 1; } } } void solve() { int x; std::cin >> x; int dmin = x; std::vector<int> ans; for (int a = 1; a < x; ++a) { int b = x - a; int fa = a - pcnt[a], fb = b - pcnt[b]; int d = std::abs(fa - fb); if (d < dmin) { dmin = d; ans.clear(); } if (d == dmin) ans.push_back(a); } for (auto a : ans) { std::cout << a << " " << x - a << std::endl; } } int main() { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios::sync_with_stdio(false); init(); solve(); return 0; }