java - InterviewStreet 不友好数字 java

Question

关于这个问题的更多信息，请看这里:https://www.interviewstreet.com/challenges/dashboard/#problem/4f7272a8b9d15

有一个友好号码和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。

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

我使用埃拉托色尼筛法来精炼不友好的数字(删除重复项，在给定示例中删除不必要的数字，如 2 和 4。除以 2 和 4 的数字也可以除以 8，因此只有 8 可以达到目的。做完之后所有这些我都删除了素数)

这是我的代码

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 个测试用例。有人请帮忙。

提前致谢

Answer 1

您只需生成 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;