首先是一个小的澄清。我确实在这个问题上得到了 AC，但我更好的方法（这在数学上是等效的，我假设我的 AC 解决方案）是得到一个 WA 判决在 interviewstreet 中存在一个问题，如下所示：
有1个友好号码和N个不友好号码。我们想找出有多少数字正好整除友好数字，但不整除任何不友好数字。
输入格式：
输入的第一行包含两个由空格分隔的数字 N 和 K。N是不友好号码的数量，K是友好号码。输入的第二行包含 N 个空格分隔的不友好数字。
输出格式：
在一行中输出答案。
样本输入：
8 16
2 5 7 4 3 8 3 18样本输出：
1
解释：
给定友好数字 16 的除数是 { 1, 2, 4, 8, 16 }，不友好数字是 { 2, 5, 7, 4, 3, 8, 3, 18 }。现在1整除所有不友好的数字，2整除2，4整除4，8整除8，但16不整除任何一个。因此，只有一个数字可以整除友好数字，但不整除任何不友好数字。所以答案是1。
我的算法（得到了 AC）如下：
让可能的不友好数字输入[i] where 0<=i
对于每个 input[i] 找到 gcd(input[i],k)。
将范围 (0,n) 中所有 i 的 gcd(input[i],k) 的所有因子存储在一个集合中。让我们将此集合称为可能因子。
对于 k 的每个因子，检查它是否除掉了可能因子中的任何元素。如果否，则增加答案计数
我修改了算法，假设如下：
不是将 gcd(input[i],k) 的所有因子存储在一个集合中，而是找出范围 (0,n) 中所有 i 的 gcd(input[i],k) 的 lcm。这可以通过以下 LOC 轻松完成
lcm = (lcm/gcd(gcd(input[i],k),lcm))*(gcd(input[i],k))
现在对于 k 的所有因素，检查它们是否划分 lcm。如果没有，则增加计数。
然而，这个假设给了我 WA。是因为我的逻辑有任何缺陷吗？如果是，请指出（如果可能，用数学证明）这两种方法有何不同？
这是我的代码，第二种方法供参考（以及可能的错误）
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
typedef long long LL;
LL gcd(LL a,LL b) {
LL c;
while(b) {
c=a%b;
a=b;
b=c;
}
return a;
}
int main()
{
long long int n,k,i,x,j,ans=0,a,num,g;
scanf("%lld%lld",&n,&k);
num=1;
for(i=0;i<n;i++) {
scanf("%lld",&a);
g=gcd(a,k);
num=(num/gcd(num,g))*g;
}
x=sqrt(k);ans=0;
for(i=1;i<=x;i++) {
if(!(k%i)) {
if((num%i)) ans++;
if((k/i != i) && (num%(k/i))) ans++;
}
}
printf("%lld\n",ans);
return 0;
}