Advertisement
romas71rus

Task 3

May 17th, 2022
545
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef unsigned long long ll;
  4. ll pows[70];
  5. const ll INF = 1e10 + 89;
  6. void fil() {
  7.     pows[0] = 1ll;
  8.     for (int i = 1; i <= 63; ++i)
  9.         pows[i] = pows[i - 1] * 2ll;
  10. }
  11. ll mul_mod(ll a, ll b, ll mod) {
  12.     ll res = 0;
  13.     while (b) {
  14.         if (b & 1)
  15.             res = (res + a) % mod;
  16.         a = (a * 2ll) % mod;
  17.         b >>= 1;
  18.     }
  19.     return res;
  20. }
  21. ll powm(ll p, ll n, ll mod) {
  22.     ll res = 1;
  23.     while (n) {
  24.         if (n & 1)
  25.             res = mul_mod(res, p, mod);
  26.         p = mul_mod(p, p, mod);
  27.         n >>= 1;
  28.     }
  29.     return res;
  30. }
  31. bool mrt(ll p) {
  32.     if (p == 1)
  33.         return false;
  34.     ll s = 0, d = p - 1;
  35.     while (!(d & 1)) {
  36.         d = d / 2;
  37.         s++;
  38.     }
  39.     srand(time(NULL));
  40.     for (int i = 1; i <= 5; ++i) {
  41.         ll a = rand() % p;
  42.         if (a == 0)
  43.             a++;
  44.         bool flag1 = false, flag2 = false;
  45.         if (powm(a % p, d, p) == 1)
  46.             flag1 = true;
  47.         if (!flag1)
  48.             for (int r = 0; r < s; ++r)
  49.                 if (powm(a % p, pows[r] * d, p) == p - 1)
  50.                     flag2 = true;
  51.         if (!flag1 && !flag2)
  52.             return false;
  53.     }
  54.     return true;
  55. }
  56.  
  57. int main() {
  58.      ll m, n;
  59.     int div = 2;
  60.     fil();
  61.     cin >> m;
  62.     if (mrt(m)){
  63.         cout << m;
  64.        
  65. }
  66.     else{
  67.         while (m > 1) {
  68.             int k = 0;
  69.             while (m % div == 0) {
  70.                 k++;
  71.                 m = m / div;
  72.             }
  73.             if (k > 0) {
  74.                 cout << div;
  75.                 if (k > 1) cout << " " << k;
  76.                 if (m > 1) cout << " ";
  77.             }
  78.             if (div == 2) div++;
  79.             else div += 2;
  80.         }
  81.  
  82.    
  83.  
  84.     return 0;
  85. }
  86. }
Advertisement
RAW Paste Data Copied
Advertisement