test/aoj/NTL_1_A.test.cpp

• View this file on GitHub
• Last update: 2022-05-27 16:58:03+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A

Depends on

• Math/prime_factorization.cpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A"

#include <bits/stdc++.h>
#ifdef __LOCAL
#define DBG(X) cout << #X << " = " << (X) << endl;
#define SAY(X) cout << (X) << endl;
#else
#define DBG(X)
#define SAY(X)
#define NDEBUG
#endif

using namespace std;

typedef int_fast32_t int32;
typedef int_fast64_t int64;

const int32 inf = 1e9+7;
const int32 MOD = 1000000007;
const int64 llinf = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define all(obj) (obj).begin(),(obj).end()
#define rall(obj) (obj).rbegin(),(obj).rend()
#define fi first
#define se second
#define pb(a) push_back(a)
typedef pair<int32,int32> pii;
typedef pair<int64,int64> pll;

template<class T> inline bool chmax(T& a, T b) {
  if (a < b) { a = b; return true; } return false;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) { a = b; return true; } return false;
}

#include "../../Math/prime_factorization.cpp"

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  cout << n << ":";
  for(auto p : prime_factorization(n)){
    REP(i,p.se){
      cout << " " << p.fi;
    }
  }
  cout << endl;
  return 0;
}

#line 1 "test/aoj/NTL_1_A.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_A"

#include <bits/stdc++.h>
#ifdef __LOCAL
#define DBG(X) cout << #X << " = " << (X) << endl;
#define SAY(X) cout << (X) << endl;
#else
#define DBG(X)
#define SAY(X)
#define NDEBUG
#endif

using namespace std;

typedef int_fast32_t int32;
typedef int_fast64_t int64;

const int32 inf = 1e9+7;
const int32 MOD = 1000000007;
const int64 llinf = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define all(obj) (obj).begin(),(obj).end()
#define rall(obj) (obj).rbegin(),(obj).rend()
#define fi first
#define se second
#define pb(a) push_back(a)
typedef pair<int32,int32> pii;
typedef pair<int64,int64> pll;

template<class T> inline bool chmax(T& a, T b) {
  if (a < b) { a = b; return true; } return false;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) { a = b; return true; } return false;
}

#line 1 "Math/prime_factorization.cpp"
vector<pair<int64,int32>> prime_factorization(int64 n){
  assert(n >= 1);
  vector<pair<int64,int32>> res;
  for(int64 p = 2; p * p <= n; ++p){
    int32 cnt = 0;
    while(n % p == 0){
      ++cnt;
      n /= p;
    }
    if(cnt > 0)res.emplace_back(p,cnt);
  }
  if(n > 1){
    res.emplace_back(n,1);
  }
  return res;
}
#line 45 "test/aoj/NTL_1_A.test.cpp"

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  cout << n << ":";
  for(auto p : prime_factorization(n)){
    REP(i,p.se){
      cout << " " << p.fi;
    }
  }
  cout << endl;
  return 0;
}

Back to top page