Bình luận

• 
  

  0

  

  megarayquara  đã bình luận lúc 25, Tháng 5, 2026, 10:58

  Đây ko phải là bài cho trẻ em nó là của chat r

  include <bits/stdc++.h>

  define int long long

  using namespace std;

  mt1993764 rng(chrono::steadyclock::now().timesinceepoch().count());

  int mulmod(int a, int b, int mod) { return (__int128)a * b % mod; }

  int powmod(int a, int b, int mod) { int res = 1; while (b) { if (b & 1) res = mulmod(res, a, mod); a = mulmod(a, a, mod); b >>= 1; } return res; }

  bool isPrime(int n) { if (n < 2) return false;

  for (int p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
      if (n % p == 0)
          return n == p;
  }
  
  int d = n - 1, s = 0;
  
  while ((d & 1) == 0) {
      d >>= 1;
      s++;
  }
  
  for (int a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
      if (a % n == 0) continue;
  
      int x = powmod(a, d, n);
  
      if (x == 1 || x == n - 1)
          continue;
  
      bool ok = false;
  
      for (int r = 1; r < s; r++) {
          x = mulmod(x, x, n);
  
          if (x == n - 1) {
              ok = true;
              break;
          }
      }
  
      if (!ok)
          return false;
  }
  
  return true;
  

  }

  int PollardRho(int n) { if (n % 2 == 0) return 2;

  int c = uniform_int_distribution<int>(1, n - 1)(rng);
  int x = uniform_int_distribution<int>(0, n - 1)(rng);
  int y = x;
  int d = 1;
  
  auto f = [&](int x) {
      return (mulmod(x, x, n) + c) % n;
  };
  
  while (d == 1) {
      x = f(x);
      y = f(f(y));
  
      d = gcd(abs(x - y), n);
  }
  
  if (d == n)
      return PollardRho(n);
  
  return d;
  

  }

  map<int,int> mp;

  void factor(int n) { if (n == 1) return;

  if (isPrime(n)) {
      mp[n]++;
      return;
  }
  
  int d = PollardRho(n);
  
  factor(d);
  factor(n / d);
  

  }

  signed main() { ios::syncwithstdio(false); cin.tie(nullptr);

  int n;
  cin >> n;
  
  factor(n);
  
  for (auto x : mp)
      cout << x.first << ' ' << x.second << '\n';
  

  }