Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- *
- * 根据唯一分解定理,每个正整数n都可以唯一的表示为 n=2q03q15q2…piqi…
- * 其中pi是第i小的质数,qi是pi的指数(>=0)。
- * 也就是说每一个正整数n可以唯一的对应到一个数列q0,q1,…,qi,…。
- * 给定一个数组a0,a1,…,am−1,请把数组按照每个数对应的数列的字典序排序。
- *
- */
- #include <cmath>
- #include <cstring>
- #include <iostream>
- unsigned primes(unsigned max, unsigned** factors)
- {
- if (max < 2) {
- return -1;
- }
- // find all prime factors
- bool* is_composite = new bool[max + 1] { false };
- double sup = sqrt(max) + 1;
- for (size_t i = 3; i <= sup; i += 2) {
- if (!is_composite[i]) {
- for (size_t j = 3; i * j <= max; j += 2) {
- is_composite[i * j] = true;
- }
- }
- }
- // calculate the number of prime factors
- unsigned count = 1;
- for (size_t i = 3; i <= max; i += 2) {
- count += !is_composite[i];
- }
- // allocate space and fill in the prime factors
- if (factors != nullptr) {
- *factors = new unsigned[count];
- unsigned index = 0;
- (*factors)[index++] = 2;
- for (size_t i = 3; i <= max; i += 2) {
- if (!is_composite[i]) {
- (*factors)[index++] = i;
- }
- }
- }
- delete[] is_composite;
- return count;
- }
- void prime_factorize(unsigned n, unsigned* primes, unsigned prime_cnt, unsigned* exponents)
- {
- memset(exponents, 0, prime_cnt * sizeof(unsigned));
- for (size_t i = 0; i < prime_cnt; i++) {
- while (n % primes[i] == 0) {
- exponents[i]++;
- n /= primes[i];
- }
- }
- }
- bool gt(unsigned* arr1, unsigned* arr2, unsigned cnt)
- {
- if (cnt == 0) {
- return false;
- }
- if (*arr1 > *arr2) {
- return true;
- } else if (*arr1 < *arr2) {
- return false;
- } else {
- return gt(arr1 + 1, arr2 + 1, cnt - 1);
- }
- }
- template <class T>
- void swap(T& a, T& b)
- {
- T tmp = b;
- b = a;
- a = tmp;
- }
- void sort(unsigned* index, unsigned** aoa, unsigned row, unsigned col)
- {
- for (size_t i = 0; i < row; i++) {
- for (size_t j = i + 1; j < row; j++) {
- if (gt(aoa[i], aoa[j], col)) {
- swap(aoa[i], aoa[j]);
- swap(index[i], index[j]);
- }
- }
- }
- }
- int main(int argc, char const* argv[])
- {
- unsigned* factors = nullptr;
- unsigned factors_cnt = primes(100, &factors);
- unsigned N;
- std::cin >> N;
- unsigned* numbers = new unsigned[N];
- unsigned** exponent_matrix = new unsigned* [factors_cnt] { nullptr };
- for (size_t i = 0; i < N; i++) {
- std::cin >> numbers[i];
- exponent_matrix[i] = new unsigned[factors_cnt];
- prime_factorize(numbers[i], factors, factors_cnt, exponent_matrix[i]);
- }
- sort(numbers, exponent_matrix, N, factors_cnt);
- for (size_t i = 0; i < N; i++) {
- std::cout << numbers[i] << " ";
- }
- std::cout << std::endl;
- if (factors != nullptr) {
- delete[] factors;
- }
- delete[] numbers;
- for (size_t i = 0; i < N; i++) {
- delete[] exponent_matrix[i];
- }
- delete[] exponent_matrix;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement