跳至正文

NOIP_2001.PJ2:最大公约数与最小公倍数问题 解题报告

  • OI路程

看到这个题目,不知道怎么做,到网上搜了下最小公倍数和最大公约数之间的公式,就找到了思路,p q = x0 y0..那么我就枚举所有的p,然后求出q,再判断之间的最大公约数是不是x0,就Ok了。

#include <stdio.h>

int gcd(int x, int y)
{
 int t;
 while(y > 0){
 t = x % y;
 x = y;
 y = t;
 }
 return x;
}

int main(void)
{
 int i, ans = 0; //忘记初始化了... 
 int x, y, t, s;
 scanf(%d%d, &x, &y);
 t = x * y;
 for(i = x; i <= y; i += x){
 s = t / i;
 if((s * i == t) && (gcd(s, i) == x)){
 ans++;
 }
 }
 printf(%d\\n, ans);
 return 0;
}

发表回复

您的电子邮箱地址不会被公开。