結果
問題 |
No.1006 Share an Integer
|
ユーザー |
![]() |
提出日時 | 2020-03-06 22:29:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 2,000 ms |
コード長 | 2,217 bytes |
コンパイル時間 | 2,044 ms |
コンパイル使用メモリ | 186,844 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-14 08:07:52 |
合計ジャッジ時間 | 3,056 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for(int i = 0; i < n; ++i) #define rrep(i, n) for(int i = n-1; i >= 0; --i) #define fi first #define se second using namespace std; using lint = long long; using uint = unsigned int; using ulint = unsigned long long; using ldouble = long double; using pii = pair<int, int>; using pli = pair<lint, lint>; using pdd = pair<double, double>; using pld = pair<ldouble, ldouble>; using v1i = vector<int>; using v1li = vector<lint>; using v2i = vector<vector<int>>; using v2li = vector<vector<lint>>; using v3i = vector<vector<vector<int>>>; using v3li = vector<vector<vector<lint>>>; using v1b = vector<bool>; using v2b = vector<vector<bool>>; using v3b = vector<vector<vector<bool>>>; using v1c = vector<char>; using v2c = vector<vector<char>>; using v3c = vector<vector<vector<char>>>; constexpr lint mod1 = 1e9+7; int f(int n, v1i v){ map<int, int> m; int a = n, s = 1; rep(i, v.size()){ if(v[i] > pow(n, 0.5)) break; int b = 0; while(a % v[i] == 0){ a /= v[i]; ++b; } if(b != 0) m[v[i]] = b; if(a == 1) break; } if(a != 1 && !m.count(a)) m[a] = 1; for(auto c: m){ s *= c.se+1; } return n-s; } int main() { v1i r = {2}; rep(i, 1e3*2){ if(i > 2){ bool b = 1; rep(j, r.size()){ if(r[j] > pow(i, 0.5)) break; else if(i % r[j] == 0){ b = 0; break; } } if(b) r.push_back(i); } } int x, m; cin >> x; vector<pii> v; if(x < 2000){ rep(i, x/2){ v.push_back(make_pair(abs(f(i+1, r) - f(x-i-1, r)), i+1)); if(i+1 != x-i-1) v.push_back(make_pair(abs(f(i+1, r) - f(x-i-1, r)), x-i-1)); } } else{ for(int i = x/2-1000; i <= x/2; ++i){ v.push_back(make_pair(abs(f(i, r) - f(x-i, r)), i)); if(i != x-i) v.push_back(make_pair(abs(f(i, r) - f(x-i, r)), x-i)); } } sort(v.begin(), v.end()); m = v[0].fi; rep(i, v.size()) if(v[i].fi == m) cout << v[i].se << " " << x-v[i].se << endl; return 0; }