很有趣的一個數學問題，這一周看完《背包九講》后，就開始看CCF出的NOIP2001-2003的題解.之前認為很水的題目的最優(yōu)算法相當精妙，這進一步認證了僅僅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
}