結果

問題 No.1006 Share an Integer
ユーザー wawawa113wawawa113
提出日時 2022-06-06 17:50:16
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 839 ms / 2,000 ms
コード長 7,660 bytes
コンパイル時間 2,138 ms
コンパイル使用メモリ 163,100 KB
実行使用メモリ 299,336 KB
最終ジャッジ日時 2023-10-21 03:39:36
合計ジャッジ時間 14,037 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 251 ms
253,424 KB
testcase_01 AC 250 ms
253,212 KB
testcase_02 AC 248 ms
253,212 KB
testcase_03 AC 244 ms
253,212 KB
testcase_04 AC 256 ms
253,400 KB
testcase_05 AC 240 ms
253,264 KB
testcase_06 AC 239 ms
253,264 KB
testcase_07 AC 236 ms
253,264 KB
testcase_08 AC 238 ms
253,264 KB
testcase_09 AC 237 ms
253,264 KB
testcase_10 AC 244 ms
253,264 KB
testcase_11 AC 559 ms
278,900 KB
testcase_12 AC 812 ms
296,448 KB
testcase_13 AC 823 ms
299,212 KB
testcase_14 AC 827 ms
299,336 KB
testcase_15 AC 726 ms
292,808 KB
testcase_16 AC 469 ms
272,812 KB
testcase_17 AC 555 ms
279,676 KB
testcase_18 AC 729 ms
293,000 KB
testcase_19 AC 716 ms
291,292 KB
testcase_20 AC 770 ms
294,196 KB
testcase_21 AC 839 ms
299,212 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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(10000000);
  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.at(t).push_back(A);
  }
  sort(all(res[m]));
  for (auto i : res[m])
  {
    cout << i << " " << X - i << endl;
  }
}

// memo
// igaito maniau
0