結果
問題 | No.1006 Share an Integer |
ユーザー | wawawa113 |
提出日時 | 2022-06-06 17:47:16 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 7,560 bytes |
コンパイル時間 | 1,867 ms |
コンパイル使用メモリ | 163,248 KB |
実行使用メモリ | 36,992 KB |
最終ジャッジ日時 | 2024-09-21 04:41:51 |
合計ジャッジ時間 | 11,054 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
21,248 KB |
testcase_01 | AC | 82 ms
21,248 KB |
testcase_02 | AC | 80 ms
21,248 KB |
testcase_03 | AC | 80 ms
21,120 KB |
testcase_04 | AC | 81 ms
21,376 KB |
testcase_05 | AC | 83 ms
21,248 KB |
testcase_06 | AC | 82 ms
21,376 KB |
testcase_07 | AC | 81 ms
21,248 KB |
testcase_08 | AC | 82 ms
21,248 KB |
testcase_09 | AC | 86 ms
21,248 KB |
testcase_10 | AC | 85 ms
21,248 KB |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
ソースコード
// common part begin #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cctype> #include <cfenv> #include <cfloat> #include <chrono> #include <cinttypes> #include <climits> #include <cmath> #include <complex> #include <cstdarg> #include <cstddef> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <functional> #include <initializer_list> #include <iomanip> #include <ios> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <streambuf> #include <string> #include <tuple> #include <type_traits> #include <typeinfo> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; #define INF (1ll) << 60 #define rep(i, n) for (long long i = 0; i < n; i++) #define all(v) v.begin(), v.end() typedef long double ld; typedef long long ll; typedef unsigned long long ull; void chmax(ll &a, ll b) { if (a < b) a = b; } void chmin(ll &a, ll b) { if (a > b) { a = b; } } // common part end #define hi_ cout << "hi" << endl; #define yes cout << "yes" << endl #define no cout << "no" << endl #define Yes cout << "Yes" << endl #define No cout << "No" << endl #define llV(name, size) \ std::vector<long long> name(size); \ for (unsigned int i = 0; i < size; i++) \ cin >> name[i] #define die(x) \ cout << x << endl; \ return 0; class Print { public: Print() {} }; void operator<<(Print p, vector<ll> v) { for (auto i : v) cout << i << " "; cout << endl; } void operator<<(Print p, vector<vector<ll>> v) { for (auto i : v) { for (auto j : i) { cout << j << " "; } cout << endl; } } void operator<<(Print p, ull x) { cout << x << endl; } void operator<<(Print p, vector<ull> v) { for (auto i : v) cout << i << " "; cout << endl; } void operator<<(Print p, vector<vector<ull>> v) { for (auto i : v) { for (auto j : i) { cout << j << " "; } cout << endl; } } void operator<<(Print p, ll x) { cout << x << endl; } void operator<<(Print p, string s) { cout << s << endl; } void operator<<(Print p, vector<string> s) { for (auto i : s) cout << i << endl; } void operator<<(Print p, vector<pair<pair<ll, ll>, ll>> v) { for (auto i : v) { cout << i.first.first << " " << i.first.second << " " << i.second << endl; } } void operator<<(Print p, vector<pair<ll, pair<ll, ll>>> v) { for (auto i : v) { cout << i.first << " " << i.second.first << " " << i.second.second << endl; } } void operator<<(Print p, pair<ll, ll> v) { cout << v.first << " " << v.second << endl; } Print print; // //0-1 dfs // class Maze // { // public: // vector<vector<ll>> G; // ll H, W; // function<vector<pair<pair<ll, ll>, ll>>(pair<ll, ll>)> destination; // Maze(vector<vector<ll>> G_, function<vector<pair<pair<ll, ll>, ll>>( pair<ll, ll>)> destination_) : G(G_), H(G_.size()), W(G_.at(0).size()), destination(destination_) // { // } // void solve(pair<ll, ll> S, pair<ll, ll> T) // { // deque<pair<pair<ll, ll>, ll>> q; // q.push({S, 0}); // while (!q.empty()) // { // pair<ll, ll> now = q.front().first; // ll c = q.front().second; // q.pop(); // auto next = destination(now); // for (auto n : next) // { // } // } // } // }; // class Maze01 // { // public: // vector<vector<ll>> G; // function<vector<pair<pair<ll, ll>, ll>>(pair<ll, ll>)> destination; // ll H, W; // // 1 is # 0 is . // Maze01(vector<vector<ll>> G_, function<vector<pair<pair<ll, ll>, ll>>(pair<ll, ll>)> destination_) : G(G_), H(G.size()), W(G.at(0).size()), destination(destination_) // { // } // vector<vector<ll>> solve(pair<ll, ll> S) // { // if (G[S.first][S.second] == 1) // return vector<vector<ll>>(H, vector<ll>(W, INF)); // deque<pair<pair<ll, ll>, ll>> q; // q.push_back({S, 0}); // vector<vector<ll>> dis(H, vector<ll>(W, INF)); // dis[S.first][S.second] = 0; // while (!q.empty()) // { // auto now = q.front(); // q.pop_front(); // auto next = destination(now.first); // for (auto n : next) // { // ll h = n.first.first; // ll w = n.first.second; // ll c = n.second; // if (h < 0 || H <= h || w < 0 || w >= W) // { // continue; // } // if (dis[h][w] != INF) // continue; // if (G[h][w] == 1) // continue; // dis[h][w] = dis[now.first.first][now.first.second] + c; // if (c) // { // q.push_back({{h, w}, c}); // } // else // { // q.push_front({{h, w}, c}); // } // } // } // return dis; // } // }; // class Maze // { // public: // vector<vector<ll>> G; // function<vector<pair<ll, ll>>(pair<ll, ll>)> destination; // ll H, W; // // 1 is # 0 is . // Maze(vector<vector<ll>> G_, function<vector<pair<ll, ll>>(pair<ll, ll>)> destination_) : G(G_), H(G.size()), W(G.at(0).size()), destination(destination_) // { // } // vector<vector<ll>> solve(pair<ll, ll> S) // { // if (G[S.first][S.second] == 1) // return vector<vector<ll>>(H, vector<ll>(W, INF)); // queue<pair<ll, ll>> q; // q.push(S); // vector<vector<ll>> dis(H, vector<ll>(W, INF)); // dis[S.first][S.second] = 0; // while (!q.empty()) // { // auto now = q.front(); // q.pop(); // auto next = destination(now); // for (auto n : next) // { // if (n.first < 0 || H <= n.first || n.second < 0 || n.second >= W) // { // continue; // } // if (dis[n.first][n.second] != INF) // continue; // if (G[n.first][n.second] == 1) // continue; // dis[n.first][n.second] = dis[now.first][now.second] + 1; // q.push({n.first, n.second}); // } // } // return dis; // } // }; template <typename T> map<T, T> prime_factor(T n) { map<T, T> ret; for (T i = 2; i * i <= n; i++) { T tmp = 0; while (n % i == 0) { tmp++; n /= i; } ret[i] = tmp; } if (n != 1) ret[n] = 1; return ret; } const int N_MAX = 2000000; ll spf[N_MAX]; // smallest prime factors void prepare_factorize(){ rep(i,N_MAX) spf[i] = i; for(int p=2; p*p <= N_MAX; p++){ for(int i=p; i<N_MAX; i+=p){ if(spf[i]==i) spf[i] = p; } } } // 素因数分解 // その素因数が何個あるかのmapを返す map<ll, ll> factorize_fast(ll n){ if(spf[1]==0){ // p("please initialize"); exit(0); } map<ll, ll> mp; while(n!=1){ ll p = spf[n]; mp[p]++; n/=p; } return mp; } // 約数の種類数 // 6 => 1, 2, 3, 6なので4 ll yaku(ll n){ auto mp = factorize_fast(n); ll ret = 1; for(auto pa : mp){ ret *= (pa.second+1); } return ret; } int main() { prepare_factorize(); ll X;cin>>X; ll m=INF;vector<vector<ll>> res(100000); vector<ll> f(X+1); for(ll i=1;i<=X;i++){ f[i]=i-yaku(i); } for(ll A=1;A<=X-1;A++){ ll B=X-A; ll t=abs(f[A]-f[B]); chmin(m,t); res[t].push_back(A); } sort(all(res[m])); for(auto i:res[m]){ cout<<i<<" "<<X-i<<endl; } } // memo // igaito maniau