結果

問題 No.442 和と積
コンテスト
ユーザー yuuki arisawa
提出日時 2021-01-16 12:39:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,615 bytes
コンパイル時間 1,750 ms
コンパイル使用メモリ 183,548 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-11-27 12:36:44
合計ジャッジ時間 4,511 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

// * abc052_c
// * abc110_d
// * abc142_d
// * arc067_c
// * abc146_c
// * abc061_c
// * abc114_d
// * abc114_c
// * arc032_a
// * arc034_c
// * aoj_2706
// check list
// * variable range
// * immeditate value is int range(accumulate)
// * index range(0 origin or 1 origin)
// * input is complete?
// * unued input
// * misunderstand input(node edge and node point)
#include <bits/stdc++.h>
using namespace std;

//https://www2.slideshare.net/Roadagain/ss-71620380
//https://github.com/kurokoji/.cpp-Template/blob/master/template/template.cpp
#define int long long
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* cpp template {{{ */

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)
#define X real()
#define Y imag()

/* REPmacro */
#define REPS(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (ll i = (a); i >= (ll)(n); --i)
#define DEP(i, n) DEPS(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/* debug */
#define debug(x) cerr << #x << ":" << x << " " << "(L:" << __LINE__ << ")" << '\n';

/* alias */
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T> >;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
template <class T = int> inline T in() {T x; cin >> x; return (x);}
inline vs split(const string& t, char c) {vs v; stringstream s(t); string b; while(getline(s, b, c)) v.eb(b); return v;}
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
template <typename T, typename S> inline void print(const pair<T, S>& p) {cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << '\n';}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v) {for (auto&& p : v) print(p);}
template <typename T> inline void print(const vector<T>& v, string s = " ") {REP(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
template < typename T > void pprint(T const& a){  std::cout << " " << a ; }
template < typename... Args > void pp(Args... args){using swallow = std::initializer_list<int>; (void)swallow{ (void( pprint(args) ), 0)... }; cout << endl; }
// clang-format on
/* }}} */

string enc(long long i,long long j){
  return to_string(i)+" "+to_string(j);
}

long long gcd(long long a,long long b){
  if(b==0)return a;
  return gcd(b,a%b);
}

//long long lcm=A*B/gcd(A,B);

vector<long long> prime_factorize_(long long N) {
  vector<long long> primes(0);
  for(long long i=2;i*i<=N;i++){
    while(N%i==0){
      N/=i;
      primes.push_back(i);
    }
  }
  if(N!=1){
    primes.push_back(N);
  }
  return primes;
}

vector<pair<long long, long long> > prime_factorize(long long N) {
  vector<pair<long long, long long> > res;
  for (long long a = 2; a * a <= N; ++a) {//O(N**1/2)
    if (N % a != 0) continue;
    long long ex = 0; // 指数

    // 割れる限り割り続ける
    while (N % a == 0) {
      ++ex;
      N /= a;
    }

    // その結果を push
    res.push_back({a, ex});
  }

  // 最後に残った数について
  if (N != 1) res.push_back({N, 1});
  return res;
}
long long pow(long long a,long long b){
  if(b==0) return 1;
  if(b==1) return a;
  if(b&1==0) return pow(a*a,b>>1);
  return a*pow(a,b-1);
}
signed main() {
  int A = in();
  int B = in();

  auto pP = prime_factorize(A+B);
  auto pA = prime_factorize(A);
  auto pB = prime_factorize(B);
  unordered_map<int,int>m;
  for(auto p:pA){
    m[p.first]+=p.second;
  }
  for(auto p:pB){
    m[p.first]+=p.second;
  }
  int ret = 1;
  for(auto p:pP){
    //pp(p.first,p.second,m[p.first]);
    m[p.first]=min(p.second,m[p.first]);
    //pp(p.first,p.second,m[p.first]);
    ret *= pow(p.first,m[p.first]);
    // REP(i,m[p.first]){
    //   ret *= p.first;
    // }
  }

  cout << ret << endl;
}
0