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

zoj 1337

xiaohanyu posted @ Tue, 25 May 2010 01:47:42 +0800 in Algorithm with tags ZOJ Algorithm , 2233 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;
}

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


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee