// common part begin #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include 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 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 v) { for (auto i : v) cout << i << " "; cout << endl; } void operator<<(Print p, vector> 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 v) { for (auto i : v) cout << i << " "; cout << endl; } void operator<<(Print p, vector> 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 s) { for (auto i : s) cout << i << endl; } void operator<<(Print p, vector, ll>> v) { for (auto i : v) { cout << i.first.first << " " << i.first.second << " " << i.second << endl; } } void operator<<(Print p, vector>> v) { for (auto i : v) { cout << i.first << " " << i.second.first << " " << i.second.second << endl; } } void operator<<(Print p, pair v) { cout << v.first << " " << v.second << endl; } Print print; // //0-1 dfs // class Maze // { // public: // vector> G; // ll H, W; // function, ll>>(pair)> destination; // Maze(vector> G_, function, ll>>( pair)> destination_) : G(G_), H(G_.size()), W(G_.at(0).size()), destination(destination_) // { // } // void solve(pair S, pair T) // { // deque, ll>> q; // q.push({S, 0}); // while (!q.empty()) // { // pair now = q.front().first; // ll c = q.front().second; // q.pop(); // auto next = destination(now); // for (auto n : next) // { // } // } // } // }; // class Maze01 // { // public: // vector> G; // function, ll>>(pair)> destination; // ll H, W; // // 1 is # 0 is . // Maze01(vector> G_, function, ll>>(pair)> destination_) : G(G_), H(G.size()), W(G.at(0).size()), destination(destination_) // { // } // vector> solve(pair S) // { // if (G[S.first][S.second] == 1) // return vector>(H, vector(W, INF)); // deque, ll>> q; // q.push_back({S, 0}); // vector> dis(H, vector(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> G; // function>(pair)> destination; // ll H, W; // // 1 is # 0 is . // Maze(vector> G_, function>(pair)> destination_) : G(G_), H(G.size()), W(G.at(0).size()), destination(destination_) // { // } // vector> solve(pair S) // { // if (G[S.first][S.second] == 1) // return vector>(H, vector(W, INF)); // queue> q; // q.push(S); // vector> dis(H, vector(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 map prime_factor(T n) { map 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 factorize_fast(ll n) { if (spf[1] == 0) { // p("please initialize"); exit(0); } map 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> res(10000000); vector 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.at(t).push_back(A); } sort(all(res[m])); for (auto i : res[m]) { cout << i << " " << X - i << endl; } } // memo // igaito maniau