Задача Множители У Айрата есть число n, представленное в виде разложения на m простых множителей pi, то есть n = p1·p2·...·pm. Айрат получил секретную информацию, что произведение всех делителей n по модулю 109 + 7 — пароль от ...
Задача Множители
У Айрата есть число n, представленное в виде разложения на m простых множителей pi, то есть n = p1·p2·...·pm. Айрат получил секретную информацию, что произведение всех делителей n по модулю 109 + 7 — пароль от секретной базы данных. Теперь осталось только вычислить это значение.
Входные данные
В первой строке входных данных находится число m(1 ≤ m ≤ 200 000) — количество чисел в разложении числа n на простые множители.
Во второй строке записаны m простых чисел pi (2 ≤ pi ≤ 200 000).
Выходные данные
Выведите одно число — произведение всех делителей числа n, вычисленное по модулю 109 + 7.
Примеры тестов
входные данные
2
2 3
выходные данные
36
входные данные
3
2 3 2
выходные данные
1728
Примечание
В первом примере n = 2·3 = 6. Делителями числа 6 являются 1, 2, 3 и 6, их произведение 1·2·3·6 = 36.
Во втором примере 2·3·2 = 12. Делители числа 12 — 1, 2, 3, 4, 6 и 12. 1·2·3·4·6·12 = 1728.
Помогите реализовать задачу на с++
Гость
Ответ(ы) на вопрос:
Гость#include
using namespace std;
int main() {
int m, a;
scanf("%d", &m);
int n = 1;
for (int i = 0; i < m; i++) {
scanf("%d", &a);
n *= a;
}
long long ans = 1;
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
ans = ans * i % 1000000007;
}
}
printf("%d", ans);
return 0;
}
Не нашли ответ?
Похожие вопросы