Bình luận

• 
  

  1

  

  taidotai  đã bình luận lúc 31, Tháng 5, 2026, 15:43

  include <bits/stdc++.h>

  using namespace std;

  typedef long long ll;

  // Nhân 2 số tránh tràn 64-bit ll mul_mod(ll a, ll b, ll mod) { ll res = 0; a %= mod; while (b) { if (b & 1) res = (res + a) % mod; a = (a * 2) % mod; b >>= 1; } return res; }

  // Lũy thừa nhanh có modulo ll powmod(ll a, ll d, ll mod) { ll res = 1; a %= mod; while (d) { if (d & 1) res = mulmod(res, a, mod); a = mul_mod(a, a, mod); d >>= 1; } return res; }

  // Miller–Rabin kiểm tra nguyên tố bool isPrime(ll n, int iter = 10) { if (n < 2) return false; if (n % 2 == 0) return n == 2; if (n % 3 == 0) return n == 3; if (n % 5 == 0) return n == 5;

  ll d = n - 1;
  int s = 0;
  while (d % 2 == 0) {
      d /= 2;
      s++;
  }
  
  vector<ll> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
  
  for (ll a : primes) {
      if (a >= n) continue;
      ll x = pow_mod(a, d, n);
      if (x == 1 || x == n - 1) continue;
      bool composite = true;
      for (int r = 1; r < s; r++) {
          x = mul_mod(x, x, n);
          if (x == n - 1) {
              composite = false;
              break;
          }
      }
      if (composite) return false;
  }
  return true;
  

  }

  // Pollard's Rho tìm 1 ước số ll rho(ll n) { if (n % 2 == 0) return 2; if (n % 3 == 0) return 3;

  ll x = rand() % (n - 2) + 2;
  ll y = x;
  ll c = rand() % (n - 1) + 1;
  ll d = 1;
  
  auto f = [&](ll val) { return (mul_mod(val, val, n) + c) % n; };
  
  while (d == 1) {
      x = f(x);
      y = f(f(y));
      d = __gcd(abs(x - y), n);
      if (d == n) return rho(n);
  }
  return d;
  

  }

  // Đệ quy phân tích thừa số map<ll, int> factors;

  void factorize(ll n) { if (n == 1) return; if (isPrime(n)) { factors[n]++; return; } ll d = rho(n); factorize(d); factorize(n / d); }

  int main() { srand(time(NULL)); ll n; cin >> n;

  factorize(n);
  
  for (auto [p, exp] : factors) {
      cout << p << " " << exp << endl;
  }
  
  return 0;
  

  } code full ac cho ae nao can . bai nay kho vai pia , khong don gian dau