#P2082. [Poi2010]Divine divisor

    ID: 1107 传统题 2000ms 259MiB 尝试: 355 已通过: 74 难度: 8 上传者: 标签>CF2400提高+/省选-埃氏筛试除法分解质因数欧几里得算法Miller–Rabin快速幂快速乘防溢出有序映射乘法原理高精度乘法

[Poi2010]Divine divisor

题目描述

给定由 mm 个整数 aia_i 描述的整数 N=∏i=1maiN=\prod_{i=1}^m a_i。求最大的正整数 kk,使得存在整数 d>1d>1 满足 dk∣Nd^k\mid N。同时求这个 kk 下满足条件的不同整数 dd 有多少个。

例如,N=48=24⋅3N=48=2^4\cdot 3 时,最大的 kk 为 44,仅 d=2d=2 满足条件。N=6N=6 时,最大的 kk 为 11,满足条件的 dd 为 2,3,62,3,6。

输入格式

第一行一个整数 mm。

第二行 mm 个整数 a1,a2,…,ama_1,a_2,\ldots,a_m。

输出格式

第一行输出最大的 kk。第二行输出满足条件的 dd 的个数,输出完整的十进制整数。

数据范围

1≤m≤6001\le m\le600,2≤ai≤10182\le a_i\le 10^{18}。

3
4 3 4
4
1
1
6
1
3

波兰信息学奥赛官方题集原 PDF