Найти максимальную степень простого делителя числа

@Cubomedusa1622 · Регистрация: 27.05.2022

Студворк — интернет-сервис помощи студентам

Помогите, пожалуйста, с задачей. Суть такова: сначала на вход дается целое m (< 400), после этого по очереди запрашивается m целых чисел x (1 < x <= 10¹⁸), например x = 2430, нужно найти максимальную возможную степень его простого делителя. То есть, в данном случае 2430 можно представить как 5¹ * 2¹ * 3⁵. Максимальная степень 5, следовательно ответ 5. Есть ограничение по времени 2,8 с.

Пример ввода:

3
2430
27
5

Пример вывода:

5
3
1

Код уже написан и все работает до шестого теста. Проблема в том, что по условию x <= 10¹⁸ и на одном тесте все руинится с ошибкой "time-limit-exceeded".

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include<math.h>
#include<string>
using namespace std;
 
int len = 30;
 
void Initialization_matrix(unsigned long long** m) {
    for (int i = 0; i < len; i++) {
        m[i] = new unsigned long long[2];
        m[i][0] = 0;
        m[i][1] = 0;
    }
}
 
void Decomposition(unsigned long long xx, unsigned long long** m) {
    unsigned long long i = 2; int count = 0;
    unsigned long long x = xx;
 
    while (x > 1) {
        if (x % i == 0) {
            if (m[count][1] == 0) {
                m[count][0] = i;
                m[count][1] = 1;
            }
            else m[count][1]++;
            x /= i;
        }
        else {
            i++;
            if (m[count][0] != 0) count++;
        }
    }
 
    //cout << m[count][1] << "yes" << endl;
 
    /* for (int j = 0; j < 2; j++) {
         for (i = 0; i < len; i++) cout << m[i][j] << "   ";
         cout << endl;
     }*/
 
}
 
int main()
{
    unsigned long long** m = new unsigned long long* [len];
 
    unsigned long long n;
    cin >> n;
    //cout << n << endl;
 
    for (int i = 0; i < n; i++) {
        Initialization_matrix(m);
 
        unsigned long long a = 0;
        //cout << "Enter number: ";
        cin >> a;
        //cout << a << endl;
 
        if (a <= 1) cout << to_string(a) << endl;
        else
        {
            Decomposition(a, m);
 
            unsigned long long max = 0;
            for (int i = 0; i < len; i++)
                if (m[i][0] == 0) break;
                else
                    if (max < m[i][1])
                        max = m[i][1];
 
 
            cout << max << endl;
        }
    }
 
}

@HWAA · 29.07.2022, 21:54

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <cstdint>
using namespace std;
 
int MaxStepDel(uint64_t x) {
    int maxD = 1;
    int m = 0;
    while (x % 2 == 0) {
        m++;
        x /= 2;
    }
    if (m > maxD) maxD = m;
    m = 0;
    while (x % 3 == 0) {
        m++;
        x /= 3;
    }
    if (m > maxD) maxD = m;
    m = 0;
    while (x % 5 == 0) {
        m++;
        x /= 5;
    }
    if (m > maxD) maxD = m;
    m = 0;
    while (x % 7 == 0) {
        m++;
        x /= 7;
    }
    if (m > maxD) maxD = m;
    m = 0;
    while (x % 11 == 0) {
        m++;
        x /= 11;
    }
    if (m > maxD) maxD = m;
    m = 0;
    while (x % 13 == 0) {
        m++;
        x /= 13;
    }
    if (m > maxD) maxD = m;
    m = 0;
    while (x % 17 == 0) {
        m++;
        x /= 17;
    }
    if (m > maxD) maxD = m;
    m = 0;
    while (x % 19 == 0) {
        m++;
        x /= 19;
    }
    if (m > maxD) maxD = m;
    m = 0;
    while (x % 23 == 0) {
        m++;
        x /= 23;
    }
    if (m > maxD) maxD = m;
    m = 0;
    while (x % 29 == 0) {
        m++;
        x /= 29;
    }
    if (m > maxD) maxD = m;
    m = 0;
    int rest[8] = { 1, 7, 11, 13, 17, 19, 23, 29 };
    for (int k = 0; true; k += 30) {
        int j;
        int fr;
        if (k == 0) fr = 1;
        else fr = 0;
        for (j = fr; j < 8; j++) {
            int i = k + rest[j];
            if (i * i > x) break;
            // проверка делимости и подсчет
            if (x % i == 0) {
                m = 0;
                while (x % i == 0) {
                    m++;
                    x /= i;
                }
                if (m > maxD) maxD = m;
            }
        }
        if (j < 8)   break;
    }
    return maxD;
}
int main() {
    int t; cin >> t;
    for (int i = 0; i < t; i++) {
        uint64_t a = 0;
        cin >> a;
        cout << MaxStepDel(a) << endl;
    }
}

Добавлено через 35 секунд
все равно WA только на другом тесте

@depressed0yokid · 30.07.2022, 07:04

HWAA, в тестирующих системах, если решение работает дольше ТЛ, то оно просто сразу завершается.

Добавлено через 2 часа 10 минут
При помощи решета Эратосфена найдем все простые числа до 10^6(включительно), так мы обработает все степени не меньшие 3. Осталось 2 возможных ответа: 1 или 2. Ответ 2, если число является полным квадратом, эту проверку можно выполнить при помощи двоичного поиска(или что корень - целое число). В остальных случаях ответ 1, так как либо число x простое, либо x=p*q, p и q - простые.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <vector>
using namespace std;
 
const int MAX_SQRT = 1000000000;
const int MAX_CBRT = 1000000;
 
bool isSquare(int64_t x) {
    int left = 0, right = MAX_SQRT;
    while (right - left > 1) {
        int mid = (left + right) / 2;
        if ((int64_t)mid * mid >= x) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return (int64_t)right * right == x;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    vector<bool> isPrime(MAX_CBRT + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= MAX_CBRT; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= MAX_CBRT; j += i) {
                isPrime[j] = false;
            }
        }
    }
    vector<int> primes;
    for (int i = 2; i <= MAX_CBRT; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
 
    int m;
    cin >> m;
    while (m--) {
        int64_t x;
        cin >> x;
        int maxPow = (isSquare(x) ? 2 : 1);
        for (int p : primes) {
            int curPow = 0;
            while (x % p == 0) {
                x /= p;
                curPow++;
            }
            maxPow = max(maxPow, curPow);
        }
        cout << maxPow << '\n';
    }
}

@TheCalligrapher · 30.07.2022, 07:30

Сообщение от depressed0yokid

Ответ 2, если число является полным квадратом

С чего бы это вдруг? А как же числа вида p²*q? Они не являются полными квадратами, но для них ответ 2.

Чтобы ваша таблица не спасла ситуацию, составим число вида p²*q, где p > 10⁶ и запустим в вашу программу. Например: 1000003 * 1000003 * 5 = 5000030000045. Ваша программа дает ответ 1. А правильный ответ: 2.

@depressed0yokid · 30.07.2022, 07:33

TheCalligrapher, тупанул, но чтобы это исправить достаточно проверку на полный квадрат перенести после for'a.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
 
const int MAX_SQRT = 1000000000;
const int MAX_CBRT = 1000000;
 
bool isSquare(int64_t x) {
    int left = 0, right = MAX_SQRT;
    while (right - left > 1) {
        int mid = (left + right) / 2;
        if ((int64_t)mid * mid >= x) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return (int64_t)right * right == x;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    vector<bool> isPrime(MAX_CBRT + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= MAX_CBRT; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= MAX_CBRT; j += i) {
                isPrime[j] = false;
            }
        }
    }
    vector<int> primes;
    for (int i = 2; i <= MAX_CBRT; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
 
    int m;
    cin >> m;
    while (m--) {
        int64_t x;
        cin >> x;
        int maxPow = 1;
        for (int p : primes) {
            int curPow = 0;
            while (x % p == 0) {
                x /= p;
                curPow++;
            }
            maxPow = max(maxPow, curPow);
        }
        if (x != 1 && isSquare(x)) {
            maxPow = max(maxPow, 2);
        }
        cout << maxPow << '\n';
    }
}

Новые блоги и статьи Все статьи Все блоги /
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .