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

@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';
    }
}

Новые блоги и статьи Все статьи Все блоги /
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/