zoj 1337 - 行者无疆始于足下 - 行走，思考，在路上

zoj 1337

xiaohanyu posted @ Tue, 25 May 2010 01:47:42 +0800 in Algorithm with tags ZOJ Algorithm , 3469 readers

简单题，不知道为什么开始WA了一下。

题目大意是给定一组n个数，那么共有n(n-1)/2个数对，求出所有的互质数对，就是这样。gcd的写法还是值得背下来的。

代码：

#include <stdio.h>
#include <math.h>
 
int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}
 
int main(int argc, char *argv[])
{
    int num;
    int inta[60];
    int i, j;
    int result;
 
    while (scanf("%d", &num))
    {
        if (num == 0)
        {
            break;
        }
         
        for (i = 0; i < num; ++i)
        {
            scanf("%d", &inta[i]);
        }
 
        result = 0;
         
        for (i = 0; i < num; ++i)
        {
            for (j = i + 1; j < num; ++j)
            {
                if (gcd(inta[i], inta[j]) == 1)
                {
                    result++;
                }
            }
        }
 
        if (result == 0)
        {
            printf ("No estimate for this data set.\n");
        }
        else
        {
            printf ("%.6lf\n", sqrt(3.0*num*(num-1)/result));
        }
         
    }
     
    return 0;
}

时间紧迫，继续水题……太不道德了……

Relative Posts

Comments (0)

行者无疆 始于足下

zoj 1337 - 行者无疆 始于足下 - 行走，思考，在路上

zoj 1337

行者无疆始于足下

zoj 1337 - 行者无疆始于足下 - 行走，思考，在路上