Guest User

Untitled

a guest
Nov 8th, 2024
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.37 KB | None | 0 0
  1. #include <algorithm>
  2. #include <vector>
  3. #include <iostream>
  4. #include <map>
  5.  
  6. #define mul_mod(A, B, M) (((A) * (B)) % (M))
  7.  
  8. /*unsigned long long mul_mod(unsigned long long a, unsigned long long b, unsigned long long mod)
  9. {
  10.     return (unsigned long long)(((unsigned __int128)a * (unsigned __int128)b) % ((unsigned __int128)mod));
  11. }*/
  12.  
  13. unsigned long long pow_mod(unsigned long long b, unsigned long long e, unsigned long long mod)
  14. {
  15.     unsigned long long ans = 1;
  16.     for (; e; b = mul_mod(b, b, mod), e >>= 1)
  17.         if (e & 1) ans = mul_mod(ans, b, mod);
  18.     return ans;
  19. }
  20.  
  21. bool is_prime_miller_rabin(unsigned long long n)
  22. {
  23.     if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
  24.    
  25.     unsigned long long A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, s = __builtin_ctzll(n - 1), d = n >> s;
  26.        
  27.     for (unsigned long long a : A)
  28.     {  
  29.         unsigned long long p = pow_mod(a % n, d, n), i = s;
  30.         while (p != 1 && p != n - 1 && a % n && i--)
  31.             p = mul_mod(p, p, n);
  32.         if (p != n - 1 && i != s)
  33.             return 0;
  34.     }
  35.     return 1;
  36. }
  37.  
  38. template <class T>
  39. T gcd(T a, T b)
  40. {
  41.     return b != T(0) ? gcd(b, a % b) : a;
  42. }
  43.  
  44. unsigned long long pollard(unsigned long long n)
  45. {
  46.     unsigned long long x = 0, y = 0, t = 30, prd = 2, i = 1, q;
  47.     auto f = [&](unsigned long long x) { return mul_mod(x, x, n) + i; };
  48.    
  49.     while (t++ % 40 || gcd(prd, n) == 1)
  50.     {
  51.         if (x == y) x = ++i, y = f(x);
  52.        
  53.         if ((q = mul_mod(prd, std::max(x, y) - std::min(x, y), n)))
  54.             prd = q;
  55.        
  56.         x = f(x);
  57.         y = f(f(y));
  58.     }
  59.    
  60.     return gcd(prd, n);
  61. }
  62.  
  63. std::vector<unsigned long long> factor_integer(unsigned long long n)
  64. {
  65.     if (n == 1) return {};
  66.     if (is_prime_miller_rabin(n)) return {n};
  67.    
  68.     auto x = pollard(n);
  69.    
  70.     auto l = factor_integer(x), r = factor_integer(n / x);
  71.     l.insert(l.end(), r.begin(), r.end());
  72.    
  73.     return l;
  74. }
  75.  
  76. int main()
  77. {
  78.     std::ios::sync_with_stdio(0);
  79.     std::cin.tie(0);
  80.    
  81.     int n;
  82.     std::cin >> n;
  83.    
  84.     for (int i = 0; i < n; i++)
  85.     {
  86.         unsigned long long a;
  87.         std::cin >> a;
  88.        
  89.         auto f = factor_integer(a);
  90.         std::map<unsigned long long, int> map;
  91.        
  92.         for (auto x : f) map[x]++;
  93.        
  94.         std::string ans;
  95.         for (auto &it : map)
  96.         {
  97.             if (ans.size())
  98.                 ans += " * ";
  99.             std::string loc = std::to_string(it.first);
  100.             if (it.second > 1)
  101.                 loc += " ^ " + std::to_string(it.second);
  102.             ans += loc;
  103.         }
  104.        
  105.         std::cout << a << " = " << ans << '\n';
  106.     }
  107.    
  108.     return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment