まず第一に、小さな説明です。私はこの問題で AC を取得しましたが、私のより良いアプローチ (これは数学的に同等であり、AC ソリューションと仮定します) は WA の評決を得ることです。
1 つの友好的な番号と N の非友好的な番号があります。友好的な数を正確に分割し、非友好的な数を分割しない数がいくつあるかを見つけたいと考えています。
入力フォーマット:
入力の最初の行には、スペースで区切られた 2 つの数値 N と K が含まれています。N は友好的でない番号の数、K は友好的な番号です。入力の 2 行目には、スペースで区切られた N 個の不適切な数字が含まれています。
出力フォーマット：
答えを 1 行で出力します。
サンプル入力:
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 です。
私のアルゴ（ACを取得した）は次のとおりです。
0<=i である可能性のある不適切な数値を input[i]
各input[i]について、gcd(input[i],k)を見つけます。
セット内の範囲 (0,n) 内のすべての i について、gcd(input[i],k) のすべての因子を格納します。このセットを、PossibleFactors と呼びましょう。
k の因子ごとに、PossibleFactor のいずれかの要素を除算するかどうかを確認します。「いいえ」の場合は、回答数を増やします
以下を想定してアルゴリズムを修正しました。
gcd(input[i],k) のすべての因数を set に格納する代わりに、範囲 (0,n) 内のすべての i について gcd(input[i],k) の lcm を見つけます。これは、次の LOC で簡単に実行できます。
lcm = (lcm/gcd(gcd(input[i],k),lcm))*(gcd(input[i],k))
ここで、k のすべての因数について、それらが lcm を分割するかどうかを確認します。そうでない場合は、カウントを増やします。
しかし、この仮定は私にWAを与えています。それは私の論理に欠陥があるためですか？はいの場合、2つのアプローチの違いを（可能であれば数学的な証明で）指摘してください。
参照用の2番目のアプローチを使用したコードを次に示します（およびバグの可能性があります）
#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;
}