很有趣的一个数学问题，这一周看完《背包九讲》后，就开始看CCF出的NOIP2001-2003的题解.之前认为很水的题目的最优算法相当精妙，这进一步认证了仅仅AC是不够的，还需要进一步研究算法.
题意略.需要注意的是，题目仅仅需要求出符合条件的数对的个数，而非答案.
因而，我们可以利用一些数学分析得到一个非常简洁的结论：
以x0,y0分别为最大公约数和最大公倍数的数对个数为2^n，n是y0/x0的不同质因子个数.
1
#include<stdio.h>
2int main()
3
{
4
int x0, y0, x, i = 2, k = 0;
5 scanf(“%d%d”, &x0, &y0);
6
if (y0 % x0 != 0) {printf(“0\n”); return 0;}
7 x = y0 / x0;
8 while (x != 1)
9 {
10 while (x % i != 0) i++; k++;
11 while (x % i == 0) x /= i;
12
}
13 printf(“%d\n”, 1<<(k));
14
}