Taraxacum

PrimeFactorizeDictionaryOrder

Nov 27th, 2020
622
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *
  3.  * 根据唯一分解定理,每个正整数n都可以唯一的表示为 n=2q03q15q2…piqi…
  4.  * 其中pi是第i小的质数,qi是pi的指数(>=0)。
  5.  * 也就是说每一个正整数n可以唯一的对应到一个数列q0,q1,…,qi,…。
  6.  * 给定一个数组a0,a1,…,am−1,请把数组按照每个数对应的数列的字典序排序。
  7.  *
  8.  */
  9.  
  10. #include <cmath>
  11. #include <cstring>
  12. #include <iostream>
  13.  
  14. unsigned primes(unsigned max, unsigned** factors)
  15. {
  16.     if (max < 2) {
  17.         return -1;
  18.     }
  19.  
  20.     // find all prime factors
  21.  
  22.     bool* is_composite = new bool[max + 1] { false };
  23.     double sup = sqrt(max) + 1;
  24.  
  25.     for (size_t i = 3; i <= sup; i += 2) {
  26.         if (!is_composite[i]) {
  27.             for (size_t j = 3; i * j <= max; j += 2) {
  28.                 is_composite[i * j] = true;
  29.             }
  30.         }
  31.     }
  32.  
  33.     // calculate the number of prime factors
  34.  
  35.     unsigned count = 1;
  36.  
  37.     for (size_t i = 3; i <= max; i += 2) {
  38.         count += !is_composite[i];
  39.     }
  40.  
  41.     // allocate space and fill in the prime factors
  42.  
  43.     if (factors != nullptr) {
  44.         *factors = new unsigned[count];
  45.  
  46.         unsigned index = 0;
  47.         (*factors)[index++] = 2;
  48.  
  49.         for (size_t i = 3; i <= max; i += 2) {
  50.             if (!is_composite[i]) {
  51.                 (*factors)[index++] = i;
  52.             }
  53.         }
  54.     }
  55.  
  56.     delete[] is_composite;
  57.     return count;
  58. }
  59.  
  60. void prime_factorize(unsigned n, unsigned* primes, unsigned prime_cnt, unsigned* exponents)
  61. {
  62.     memset(exponents, 0, prime_cnt * sizeof(unsigned));
  63.  
  64.     for (size_t i = 0; i < prime_cnt; i++) {
  65.         while (n % primes[i] == 0) {
  66.             exponents[i]++;
  67.             n /= primes[i];
  68.         }
  69.     }
  70. }
  71.  
  72. bool gt(unsigned* arr1, unsigned* arr2, unsigned cnt)
  73. {
  74.     if (cnt == 0) {
  75.         return false;
  76.     }
  77.  
  78.     if (*arr1 > *arr2) {
  79.         return true;
  80.     } else if (*arr1 < *arr2) {
  81.         return false;
  82.     } else {
  83.         return gt(arr1 + 1, arr2 + 1, cnt - 1);
  84.     }
  85. }
  86.  
  87. template <class T>
  88. void swap(T& a, T& b)
  89. {
  90.     T tmp = b;
  91.     b = a;
  92.     a = tmp;
  93. }
  94.  
  95. void sort(unsigned* index, unsigned** aoa, unsigned row, unsigned col)
  96. {
  97.     for (size_t i = 0; i < row; i++) {
  98.         for (size_t j = i + 1; j < row; j++) {
  99.             if (gt(aoa[i], aoa[j], col)) {
  100.                 swap(aoa[i], aoa[j]);
  101.                 swap(index[i], index[j]);
  102.             }
  103.         }
  104.     }
  105. }
  106.  
  107. int main(int argc, char const* argv[])
  108. {
  109.     unsigned* factors = nullptr;
  110.     unsigned factors_cnt = primes(100, &factors);
  111.  
  112.     unsigned N;
  113.     std::cin >> N;
  114.  
  115.     unsigned* numbers = new unsigned[N];
  116.     unsigned** exponent_matrix = new unsigned* [factors_cnt] { nullptr };
  117.  
  118.     for (size_t i = 0; i < N; i++) {
  119.         std::cin >> numbers[i];
  120.         exponent_matrix[i] = new unsigned[factors_cnt];
  121.         prime_factorize(numbers[i], factors, factors_cnt, exponent_matrix[i]);
  122.     }
  123.  
  124.     sort(numbers, exponent_matrix, N, factors_cnt);
  125.  
  126.     for (size_t i = 0; i < N; i++) {
  127.         std::cout << numbers[i] << " ";
  128.     }
  129.     std::cout << std::endl;
  130.  
  131.     if (factors != nullptr) {
  132.         delete[] factors;
  133.     }
  134.  
  135.     delete[] numbers;
  136.  
  137.     for (size_t i = 0; i < N; i++) {
  138.         delete[] exponent_matrix[i];
  139.     }
  140.  
  141.     delete[] exponent_matrix;
  142.  
  143.     return 0;
  144. }
  145.  
RAW Paste Data