#768705 (C++17) No.1006 Share an Integer

提出ソース

結果

問題	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
コンパイル時間	2,678 ms
コンパイル使用メモリ	162,992 KB
実行使用メモリ	37,124 KB
最終ジャッジ日時	2023-10-21 03:39:04
合計ジャッジ時間	12,665 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	79 ms 21,328 KB
testcase_01	AC	80 ms 21,328 KB
testcase_02	AC	80 ms 21,328 KB
testcase_03	AC	80 ms 21,328 KB
testcase_04	AC	79 ms 21,328 KB
testcase_05	AC	78 ms 21,328 KB
testcase_06	AC	77 ms 21,328 KB
testcase_07	AC	77 ms 21,328 KB
testcase_08	AC	78 ms 21,328 KB
testcase_09	AC	76 ms 21,328 KB
testcase_10	AC	80 ms 21,328 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	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

// 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

yukicoder

結果

テストケース

ソースコード