結果
問題 | No.1006 Share an Integer |
ユーザー |
![]() |
提出日時 | 2020-03-06 23:06:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 1,935 bytes |
コンパイル時間 | 1,721 ms |
コンパイル使用メモリ | 179,836 KB |
実行使用メモリ | 5,632 KB |
最終ジャッジ日時 | 2024-10-14 09:35:54 |
合計ジャッジ時間 | 3,028 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long const int MAX_N = 2e6+10; const int inf = 1e9; bool arr[MAX_N]; int division[MAX_N]; set<int> se; void eratosthenes(){ for(int i = 0; i < MAX_N; i++){ arr[i] = true;} arr[0] = false; arr[1] = false; for(int i = 2; i < MAX_N; i++){ //素因数列挙 if(arr[i] ){ for(int j = 2; i*j < MAX_N; j++){ arr[i*j] = false; } } } for(int i = 0; i < (int)sqrt(MAX_N); i++){ if( arr[i] ){ se.insert(i); } } return ; } signed main(void){ int N; cin >> N; set<pair<int,int>> ans; eratosthenes(); division[1] = 1; int left = max(N/2 - (int)sqrt(N) - 10,1LL); int right = min(N/2 + (int)sqrt(N) + 10,N ); for(int i = left; i <= right; i++){ // iの約数の個数を計算しておく // N/2の√N周りらへんを計算しておけば十分そう(予想) int res = i; int s = 1LL; if( arr[res] ){ division[i] = 2; continue;} // p と 1 for(auto d : se){ if(res % d == 0 ){ int cnt = 1LL; while( res % d == 0 ){ res /= d; cnt++; } s *= cnt; if( res == 1 ){ break;} //for-脱出 }// if res%d }//for-d if( arr[res] ){ s *= 2;} division[i] = s; } int rem = inf; for(int A = left; A <= right; A++){ int B = N-A; if( A <= 0 || B <= 0 ){ continue;} int FA = A-division[A]; int FB = B-division[B]; if( rem > abs(FA-FB) ){ rem = abs(FA-FB); ans.clear(); ans.insert({A,B}); } else if( rem == abs(FA-FB) ){ ans.insert({A,B}); } } for(auto ne : ans ){ cout << ne.first << " " << ne.second << endl;} return 0; }