3

この質問の詳細については、https ://www.interviewstreet.com/challenges/dashboard/#problem/4f7272a8b9d15 を参照してください。

1 つの友好的な番号と N の非友好的な番号があります。友好的な数を正確に分割し、非友好的な数を分割しない数がいくつあるかを見つけたいと考えています。

入力形式: 入力の最初の行には、スペースで区切られた 2 つの数値 N と K が含まれます。N は友好的でない番号の数、K は友好的な番号です。入力の 2 行目には、スペースで区切られた N 個の不適切な数字が含まれています。

出力形式: 回答を 1 行で出力します。

制約:

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 つだけ存在します。したがって、答えは 1 です。

多くの人がこの質問をしましたが、完璧な答えはありませんでした。他の人が閉じているため、これは重複していません。この質問をする必要があります

エラトステネスのふるいを使用して、不親切な数字を洗練しました（重複を削除し、指定された例の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(a[i],K) には nd(K) の数があり、 nd(K) は K の約数を表すため、 set を使用するだけです。したがって、アルゴリズムには 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) を必要とします。

最後に、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非友好的な数の数で二次です。N10 6まで大きくなる可能性があるため、これは非常に遅い操作になる可能性があります。

小さいNの場合、友好的でない数値のリスト全体をチェックするのはとにかく迅速ですが、大きいNの場合、洗練には法外なコストがかかります。結論: 精製をやめてください。それは悪い考えです。

sqrt(k)を割り切れるかどうかまですべての数をチェックするよりもはるかに高速であり、割り切れる場合は非友好的な数のいずれかを割り切れるかどうかは、最初にその素因数分解からkの​​約数のリストを取得することです (が素数または 2 つの近接素数の積でない限り、その場合、どちらの方法もほぼ同じ速度です)。の約数が多い場合(考慮される約数のリストがまだ大きい場合)、 の最大公約数と次の非友好的な数を計算し、リストからすべての約数を削除することで、それらの多くを除外できる可能性があります。リストが十分に短くなったら、単純なペアごとのチェックkkkgkg

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)) の 2 つの内部ループを使用して res :) を取得します。楽しい ;）

于 2013-01-16T12:49:52.823 に答える