Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <vector>
- #include <iostream>
- #include <map>
- #define mul_mod(A, B, M) (((A) * (B)) % (M))
- /*unsigned long long mul_mod(unsigned long long a, unsigned long long b, unsigned long long mod)
- {
- return (unsigned long long)(((unsigned __int128)a * (unsigned __int128)b) % ((unsigned __int128)mod));
- }*/
- unsigned long long pow_mod(unsigned long long b, unsigned long long e, unsigned long long mod)
- {
- unsigned long long ans = 1;
- for (; e; b = mul_mod(b, b, mod), e >>= 1)
- if (e & 1) ans = mul_mod(ans, b, mod);
- return ans;
- }
- bool is_prime_miller_rabin(unsigned long long n)
- {
- if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
- unsigned long long A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, s = __builtin_ctzll(n - 1), d = n >> s;
- for (unsigned long long a : A)
- {
- unsigned long long p = pow_mod(a % n, d, n), i = s;
- while (p != 1 && p != n - 1 && a % n && i--)
- p = mul_mod(p, p, n);
- if (p != n - 1 && i != s)
- return 0;
- }
- return 1;
- }
- template <class T>
- T gcd(T a, T b)
- {
- return b != T(0) ? gcd(b, a % b) : a;
- }
- unsigned long long pollard(unsigned long long n)
- {
- unsigned long long x = 0, y = 0, t = 30, prd = 2, i = 1, q;
- auto f = [&](unsigned long long x) { return mul_mod(x, x, n) + i; };
- while (t++ % 40 || gcd(prd, n) == 1)
- {
- if (x == y) x = ++i, y = f(x);
- if ((q = mul_mod(prd, std::max(x, y) - std::min(x, y), n)))
- prd = q;
- x = f(x);
- y = f(f(y));
- }
- return gcd(prd, n);
- }
- std::vector<unsigned long long> factor_integer(unsigned long long n)
- {
- if (n == 1) return {};
- if (is_prime_miller_rabin(n)) return {n};
- auto x = pollard(n);
- auto l = factor_integer(x), r = factor_integer(n / x);
- l.insert(l.end(), r.begin(), r.end());
- return l;
- }
- int main()
- {
- std::ios::sync_with_stdio(0);
- std::cin.tie(0);
- int n;
- std::cin >> n;
- for (int i = 0; i < n; i++)
- {
- unsigned long long a;
- std::cin >> a;
- auto f = factor_integer(a);
- std::map<unsigned long long, int> map;
- for (auto x : f) map[x]++;
- std::string ans;
- for (auto &it : map)
- {
- if (ans.size())
- ans += " * ";
- std::string loc = std::to_string(it.first);
- if (it.second > 1)
- loc += " ^ " + std::to_string(it.second);
- ans += loc;
- }
- std::cout << a << " = " << ans << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment