3

有关此问题的更多信息，请查看此处：https ://www.interviewstreet.com/challenges/dashboard/#problem/4f7272a8b9d15

有1个友好号码和N个不友好号码。我们想找出有多少数字正好整除友好数字，但不整除任何不友好数字。

输入格式：输入的第一行包含两个数字 N 和 K，用空格分隔。N是不友好号码的数量，K是友好号码。输入的第二行包含 N 个空格分隔的不友好数字。

输出格式：在一行中输出答案。

约束：

1 <= N <= 10^6

1 <= K <= 10^13

1 <= unfriendly numbers <= 10^18

样本输入：

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。

很多人问过这个问题，但没有给出完美的答案。这不是重复的，因为其他人都关闭了，我要问这个问题

我使用 Eratosthenes 的筛子来优化不友好的数字（删除重复项，删除给定示例中不必要的数字，如 2 和 4。除以 2 和 4 的数字也除以 8，所以只有 8 wud 达到目的。完成所有这些后，我去除素数）

这是我的代码

import java.io.*;
import java.util.*;

public class unfriendly {
public static ArrayList<Long> refine_unfriendly(ArrayList<Long> uf){
    int n=uf.size();
    long x;
    for(int i=uf.size()-1;i>=0;i--){
        x=uf.get(i);
        for(int j=uf.size()-1;j>=0;j--){
            if(j==i)
                continue;
            if(j!=i && uf.get(j)%x==0){
                x=uf.get(j);
                uf.remove(i);
                break;
            }
            else if(j!=i && x%uf.get(j)==0){
                uf.remove(j);
                break;
            }
        }
    }
    return uf;
}

public static void print_output(long k,ArrayList<Long> uf){
    int n=uf.size(),count=0,i;
    long x,y;
    if(n==0)
        count++;
    for(x=2;x<=Math.sqrt(k);x++){
        if(k%x==0){
            for(i=0;i<n;i++){
                if(uf.get(i)%x==0)
                    break;
            }
            if(i==n)
                count++;
            if(k/x!=x){
                y=k/x;
                for(i=0;i<n;i++){
                    if(uf.get(i)%y==0)
                        break;
                }
                if(i==n)
                    count++;
            }
        }
    }
    for(i=0;i<n;i++){
        if(uf.get(i)%k==0)
            break;
    }
    if(i==n)
        count++;
    System.out.println(count);
}
public static void main(String[] args) throws Exception {
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    long k=in.nextLong();
    ArrayList<Long> uf=new ArrayList<Long>();
    for(int i=0;i<n;i++)
        uf.add(in.nextLong());
    uf=refine_unfriendly(uf);
    print_output(k,uf);
}
}

这仅解决了 6 个测试用例中的 1 个。其余的超出了时间限制。蛮力法（未精炼）解决了 3 个测试用例。有人请帮忙。

提前致谢

4

6 回答 6

3

您只需生成 K 的所有除数（它需要 sqrt(K) 时间），并且您已经创建了一个新的唯一数组 GCD(a[i],K)，因为如果友好数的除数除以不友好数，则它必须除GCD(unfriendly number,K)，所以你只需使用 set ，因为 GCD(a[i],K) 有 nd(K) 数，其中 nd(K) 代表 K 的除数。所以算法只需要 O(nd(K)^2) 时间。

Here is main body of my code :

for(int i=1;i<=n;i++)
    mm.insert(gcd(a[i],k));

vv=(int)sqrt((double)k);

for(int i=1;i<=vv;i++)
    {
        if(k%i==0)
            {
                zz[++cur]=i;
                zz[++cur]=k/i;
            }
    }
if((ll)vv*(ll)vv==k)
    cur--;
int say=0;
for(int i=1;i<=cur;i++)
    {
        q=0;
        for(it=mm.begin();it!=mm.end();it++)
            if(*it%zz[i]==0)
                {
                    q=1;
                    break;
                }
        if(q==0)
            say++;
    }
cout<<say<<endl;
于 2013-01-07T22:26:52.520 回答
2

首先，在 F 中生成 K 的所有因子。这可以在 O(√K) 时间内天真地完成。

对于每个不友好的数字 Ui，计算 gcd(K,Ui) 并将其存储在集合 S 中。对于 N 个坏数字，这需要 O(NlogK)。

最后，我们通过找到 F 中的因子数来计算答案，这些因子是 S 中无数的因子。因为两个集合最多包含 |F| 数字，那么这需要 O(|F|^2) 时间。

于 2012-09-14T09:08:05.957 回答
1

你的提炼

for(int i=uf.size()-1;i>=0;i--){
    x=uf.get(i);
    for(int j=uf.size()-1;j>=0;j--){

N在不友好数字的数量上是二次的。由于N可能大到 10 6，这可能是一个非常慢的操作。

对于 small N，检查整个不友好数字列表无论如何都很快，对于 large N，精炼成本高得令人望而却步。结论：放弃精炼，这是个坏主意。

sqrt(k)比检查每个数字是否除以快得多k，如果是，则它是否除任何不友好的数字是首先k从其素数分解中获得除数列表（除非k是素数或两个相近素数的乘积，那么这两种方式都差不多快）。如果k有许多除数（而要考虑的除数列表仍然很大），您可以通过计算最大公约数和下一个不友好的数字来排除其中的许多g，k从g列表中删除所有除数。一旦列表变得足够短，简单的成对检查

for u in unfriendlyNumbers
    for d in divisors
        if u%d == 0
            remove d from divisors

成为更好的选择。

于 2012-09-13T20:01:48.270 回答
0

我的代码根据丹尼尔的算法

import java.io.*;
import java.util.*;

public class Solution {
public static long gcd(long a,long b){
    while (b != 0){
        long m = a % b;
        a = b;
        b = m;
    }
    return a;
}
public static ArrayList<Long> get_factors(long k){
    long x;
    ArrayList<Long> factors=new ArrayList<Long>();
    for(x=2;x<=Math.sqrt(k);x++){
        if(k%x==0){
            factors.add(x);
            if(k/x!=x){
                factors.add(k/x);
            }
        }
    }
    factors.add((long)1);
    factors.add(k);
    return factors;
}
public static void main(String[] args) throws Exception {
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    long k=in.nextLong(),g;
    long[] unf=new long[n];
    ArrayList<Long> factors=new ArrayList<Long>();
    factors=get_factors(k);
    for(int i=0;i<n;i++){
        unf[i]=in.nextLong();
        g=gcd(k,unf[i]);
        for(int j=factors.size()-1;j>=0;j--){
            if(g%factors.get(j)==0)
                factors.remove(j);
        }
    }
    if(n==0)
        System.out.println(2);
    else
        System.out.println(factors.size());
}
}
于 2012-09-15T01:04:21.900 回答
0

您可以使用 GCD 获得不友好数和友好数 k 之间的所有公约数。在）

然后得到K的所有除数，O(sqrt(K))。

然后使用 O(N*sqrt(K)) 的两个内部循环获得 res :)。请享用 ;）

于 2013-01-16T12:49:52.823 回答
0

正在运行但得分较低的代码可能是因为 findFactorsOfNumber 方法的时间复杂度更高：

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Solution {

    private Long n, k;
    private static long result = 0;
    private Set<Long> unfriendlyNumbers;

    private Solution() {
        this.unfriendlyNumbers = new HashSet<Long>();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Scanner scanner = new Scanner(System.in);
        solution.n = scanner.nextLong();
        solution.k = scanner.nextLong();
        for (long l = 0; l < solution.n; l++) {
            solution.unfriendlyNumbers.add(scanner.nextLong());
        }

        Set<Long> factors = findFactorsOfNumber(solution.k);

        // find gcd of k and each of n unfriendly numbers
        Set<Long> gcdSet = new HashSet<Long>();
        for (long unfriendlyNumber : solution.unfriendlyNumbers) {
            gcdSet.add(gcd(solution.k, unfriendlyNumber));
        }

        // check for those factors which are not the factors for any number in gcdSet
        result = factors.size();
        for (Long factor : factors) {
            for (long gcd : gcdSet) {
                if ((gcd >= factor && gcd % factor == 0)) {
                    result--;
                    break;
                }
            }
        }
        System.out.println(result);

    }

    private static Set<Long> findFactorsOfNumber(Long input) {
        long increment = 1;
        if (input % 2 != 0) {
            increment = 2;
        }
        Set<Long> list = new HashSet<Long>();
        for (long i = 1; i <= input / 2; i = i + increment) {
            if (input % i == 0) {
                list.add(i);
            }
        }
        list.add(input);
        return list;
    }

    public static long gcd(long p, long q) {
        if (q == 0) {
            return p;
        }
        return gcd(q, p % q);
    }

}
于 2013-08-28T18:52:15.557 回答