結果
問題 | No.1006 Share an Integer |
ユーザー | Haa |
提出日時 | 2020-03-06 22:56:19 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 1,436 bytes |
コンパイル時間 | 2,095 ms |
コンパイル使用メモリ | 167,108 KB |
実行使用メモリ | 36,840 KB |
最終ジャッジ日時 | 2024-04-22 10:07:42 |
合計ジャッジ時間 | 5,353 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 109 ms
36,708 KB |
testcase_01 | AC | 109 ms
36,708 KB |
testcase_02 | AC | 102 ms
36,708 KB |
testcase_03 | AC | 106 ms
36,836 KB |
testcase_04 | AC | 120 ms
36,840 KB |
testcase_05 | AC | 102 ms
36,836 KB |
testcase_06 | AC | 101 ms
36,708 KB |
testcase_07 | AC | 109 ms
36,584 KB |
testcase_08 | AC | 123 ms
36,704 KB |
testcase_09 | AC | 105 ms
36,708 KB |
testcase_10 | AC | 111 ms
36,704 KB |
testcase_11 | AC | 119 ms
36,832 KB |
testcase_12 | AC | 111 ms
36,832 KB |
testcase_13 | AC | 109 ms
36,836 KB |
testcase_14 | AC | 114 ms
36,836 KB |
testcase_15 | AC | 111 ms
36,832 KB |
testcase_16 | AC | 111 ms
36,800 KB |
testcase_17 | AC | 109 ms
36,708 KB |
testcase_18 | AC | 109 ms
36,708 KB |
testcase_19 | AC | 110 ms
36,836 KB |
testcase_20 | AC | 104 ms
36,832 KB |
testcase_21 | AC | 115 ms
36,620 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<ll, ll> P; typedef vector<ll> VI; typedef vector<VI> VVI; const ll MOD = 1000000007; const ll INF = 2147483647; const ll LINF = 9223372036854775807; #define REP(i, n) for (int i = 0; i < n; i++) #define ALL(v) v.begin(), v.end() const int MAX = 2000001; VI d(MAX,0); VI p(0); void yaku(int n, int nk, int yk, ll x){ d[x] = yk; for(int i = n;i < p.size();i++){ if(x*p[i] >= MAX){ break; } if(nk == 0){ yaku(i,1,2,p[i]); } else if(i == n){ yaku(i,nk+1,yk+(yk/(nk+1)),x*p[i]); } else{ yaku(i,1,yk*2,x*p[i]); } } } int main() { int x; cin >> x; VI f(MAX,1); p.push_back(2); int pr = 2; while(1){ for(int i = 2;i * pr < MAX;i++){ f[i*pr] = 0; } bool no = 1; for(int i = pr+1;i < MAX;i++){ if(f[i]){ pr = i; no = 0; break; } } if(no){ break; } p.push_back(pr); } yaku(0,0,0,1); int mina = INF; for(int i = 1;i <= x/2;i++){ mina = min(mina,(int)abs(i-d[i]-(x-i)+d[x-i])); } for(int i = 1;i < x;i++){ if(abs(i-d[i]-(x-i)+d[x-i]) == mina){ cout << i << ' ' << x-i << endl; } } return 0; }