很有趣的一個(gè)數(shù)學(xué)問題，這一周看完《背包九講》后，就開始看CCF出的NOIP2001-2003的題解.之前認(rèn)為很水的題目的最優(yōu)算法相當(dāng)精妙，這進(jìn)一步認(rèn)證了僅僅AC是不夠的，還需要進(jìn)一步研究算法.
題意略.需要注意的是，題目僅僅需要求出符合條件的數(shù)對的個(gè)數(shù)，而非答案.
因而，我們可以利用一些數(shù)學(xué)分析得到一個(gè)非常簡潔的結(jié)論：
以x0,y0分別為最大公約數(shù)和最大公倍數(shù)的數(shù)對個(gè)數(shù)為2^n，n是y0/x0的不同質(zhì)因子個(gè)數(shù).
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
}