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

zoj 1577

xiaohanyu posted @ Sun, 23 May 2010 02:02:51 +0800 in Algorithm with tags Algorithm ZOJ , 2957 readers

简单题，题目大意是给定两个数a、b，求x、y使得gcd(x, y) = a, lcm(x, y) = b，问由多少对这样的(x, y)，其中gcd(x, y)为x, y的最大公约数，lcm(x, y)为x,y的最小公倍数。解题思路主要利用[tex]x \times y = gcd(x, y) \times lcm(x, y)[/tex]就行了。WA了两次是因为没看清楚题意"x and y, one line for each test."，太马虎了。代码如下：

#include <stdio.h>
#include <math.h>

long gcd(long a,long b)
{
	return b ? gcd(b, a%b) : a;
}

long lcm(long a, long b)
{
    return a / gcd(a, b) * b;
}

int main(int argc, char *argv[])
{
    long a, b;
    long m;
    int sum;
    
    while(scanf("%ld%ld", &a, &b) != EOF)
    {
        if (a == b)
        {
            sum = 1;
        }
        else
        {
            m = a * b;

            sum = 0;
            int i;
        
            for (i = 1; i < sqrt(m); ++i)
            {
                if (((m % i) == 0) && (gcd(i, m/i) == a))
                {
                    sum += 1;
                }
            }

            sum *= 2;
        }    
        printf ("%d\n",sum);
    }
    return 0;
}

顺便，用了两个月的fvwm-crystal，感觉虽然轻量，但是有些细节颇有不便之处，比如每次新开窗口的时候窗口的大小和位置都“不太确定”——就是有时候窗口会覆盖底下的panel、有时候整个窗口又比整个屏幕都大……恰逢前天晚上兴奋无眠，因此便邪恶的敲了下面一条命令：