algorithm - 面试街头挑战中的错误答案

Question

首先要澄清一下。我确实在这个问题上得到了 AC，但是我更好的方法(在数学上等价，我假设我的 AC 解决方案)得到了 WA 判决 interviewstreet 中有一个问题是这样的:

There is one friendly number and N unfriendly numbers. We want to find how many numbers are there which exactly divide the friendly number, but does not divide any of the unfriendly numbers.

Input Format:

The first line of input contains two numbers N and K seperated by spaces. N is the number of unfriendly numbers, K is the friendly number. The second line of input contains N space separated unfriendly numbers.

Output Format:

Output the answer in a single line.

Sample Input:

8 16
2 5 7 4 3 8 3 18

Sample Output:

1

Explanation:

Divisors of the given friendly number 16, are { 1, 2, 4, 8, 16 } and the unfriendly numbers are { 2, 5, 7, 4, 3, 8, 3, 18 }. Now 1 divides all unfriendly numbers, 2 divides 2, 4 divides 4, 8 divides 8, but 16 divides none of them. So only one number exists which divides the friendly number but does not divide any of the unfriendly numbers. So the answer is 1.

我的算法(得到 AC)如下:

1. 让可能不友好的数字输入[i] where 0<=i

2. 对于每个 input[i] 找到 gcd(input[i],k)。

3. 将 (0,n) 范围内所有 i 的 gcd(input[i],k) 的所有因子存储在一个集合中。我们称这个集合为 PossibleFactors。

4. 对于 k 的每个因子，检查它是否能整除 PossibleFactor 中的任何元素。如果否，则增加回答的数量

我修改了算法假设如下:

与其将 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;
}

Answer 1

你说“找出 (0,n) 范围内所有 i 的 gcd(input[i],k) 的 lcm ... 现在对于 k 的所有因子检查它们是否划分 lcm。如果没有，则增加计数。”

该方法存在缺陷。考虑 k=20，U=[12,25,30] 的情况。然后 GCDs = [4,5,10] 和 LCM = 20。所以 k 的所有因子都除以 LCM，根据引用的标准导致零计数。但是 k 本身不整除任何一个 U，所以 count 应该是 1 而不是 0。