Logo CSP.ac

CSP.ac

1 s / 256 MB

#125. 【冬令营】Day3T2-数分解

统计

【问题描述】

小明有两个正整数x、y,他想把这两个数的乘积x·y写成另外两个正整数相乘的形式,即选择a、b,使得x·y=a·b。小明想通过选择合适的a、b,使得gcd(a,b)尽可能大,你

需要帮小明找到gcd(a,b)的最大值。小明觉得这个问题太简单了,他还想知道,有多少种选择a、b的方式,使得gcd(a,b)达到最大。

【输入格式】

一行两个正整数x、y

【输出格式】

输出两个数,用一个空格隔开。第一个数表示gcd(a,b)的最大值,第二个数表示使得gcd(a,b)达到最大的方案数。

【样例输入1】

5 8

【样例输出1】

2 4

【样例解释1】

5·8=40

40=2·20=4·10=10·4=20·2

注意a、b是有序的,所以2·20与20·2是两种不同的方案

【样例输入2】

20 4

【样例输出2】

4 2

【样例解释2】

20·4=80

80=4·20=20·4

注意a=x,b=y是允许的

【数据规模和约定】

对于10%的数据, 1<=x,y<=10^3

对于40%的数据, 1<=x,y<=10^6

对于100%的数据, 1<=x,y<=10^12