这道题目的关键在于怎么求两个整数的最大公约数,这里正好复习一下以前的知识,如下:

1.设整数a和b

2.如果a和b都为0,则二者的最大公约数不存在

3.如果a或b等于0,则二者的最大公约数为非0的一个

4.如果b不为0,则使得a=a,b=a%b,转到2重复执行

实现的递归代码如下:

int gcb(int a,int b)
{
if(b==)
return a;
else
return gcb(b,a%b);
}

注:这个算法的证明这里简单说明下:

1.设g为a和b的公约数

2.则存在m和k使得  a=g*m   b=g*k

3.同时利用b可表示a   a=b*l+r  (其中r为余数)

4.合并2、3中的两个式子得出   r=g*(m-l*k) (g!=0)

5.可看出a和b的公约数同时也是b和a%b(取余)的公约数

6.利用反证法我们可以得出结论:如果g是a和b的最大公约数则它也是b和a%b的最大公约数

这样就有了如上算法

这道题目的核心就是这些同时注意运用一些常识:

1.两个偶数不可能互质

2.两个差为1的整数一定互质

见ac代码:

#include <stdio.h>
#include <math.h> int c(int n)
{
return n*(n-)/;
} int gcb(int a,int b)
{
if(b==)
return a;
else
return gcb(b,a%b);
} int myabs(int a)
{
return a<?-a:a;
} int main()
{
int n,num[];
while(scanf("%d",&n)!=EOF&&n)
{
int i,j;
for(i=;i<n;i++)
scanf("%d",&num[i]);
double pairs=double(c(n)); double ncf=;
for(i=;i<n;i++)
{
for(j=i+;j<n;j++)
{
if(num[i]%==&&num[j]%==)
continue;
else if(myabs(num[i]-num[j])==)
{
ncf++;
continue;
}
else
{
if(gcb(num[i],num[j])==)
ncf++;
}
}
} if(ncf==)
printf("No estimate for this data set.\n");
else
printf("%.6lf\n",sqrt(/ncf*pairs));
} return ;
}
05-08 15:29