杭电2504又见GCD逆推最大公约数

news/2024/10/30 19:37:29/

老规矩,先上题目 杭电oj2504
题目的意思大概是:
给三个数,知道二个数的最大公约数b和其中一个数a,要求另外一个数c。
思路:首先我们应该知道所求的c一定是b的倍数,不然约不了分嘛,这样就可以不要一个一个往上推,只要加最大公约数的倍数,减小了时间复杂度。
接下来就是把最大公约数数的倍数和a一起求一下最大公约数,如果求出来的最大公约数等于b,那么大功告成,输出结果,如果不是,用while循环,继续加一倍b,继续判断,知道找到我们要求的那个c
嘻嘻,是不是简单易懂,
那就上代码吧

/*好题,最大公倍数的逆推算法,这里有个技巧可以减少时间复杂度就是
往上推的数一定是最大公倍数的倍数*/#include<stdio.h>int Fun(int n,int m)
{int t;while(n%m)    //辗转相除法求最大公约数{t = m;m = n%m;n = t;}return m;
}int main()
{int n,a,b;scanf("%d",&n);while(n--){int  i = 1;scanf("%d %d",&a,&b);i=2*b;while(Fun(a,i) != b){i += b;}printf("%d\n",i);}return 0;
}

如果有错误或者有难懂的地方请大家告诉我哦。
一起进步吖!


http://www.ppmy.cn/news/281999.html

相关文章

C2504:未定义的基类

今天在做MFC的时候&#xff0c;总是编译报错&#xff1a;error C2504 :未定义基类 我是看另一个人的博客才发现错误的。 我的错误在于 B继承A&#xff0c;A父类&#xff0c;B子类。 由于某一个功能的需要错误的在A.h中 #include"B.h",而本来由于B继承A,所以B.h中也有…

[Cisco]WLC2504版本升级记录,8.2到8.5

目前版本是cisco2504 8.2.14的版本&#xff0c; 注意&#xff1a;先升级到8.2.16以上的版本后再升级到8.5的版本&#xff0c;如果ap的型号过低&#xff0c;可能会出现同步不了镜像的问题&#xff0c;所以升级前一定要在官网上查看下版本的适用性&#xff0…

HDOJ 2504

又见GCD Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 14717 Accepted Submission(s): 6161 Problem Description 有三个正整数a,b,c(0<a,b,c<10^6)&#xff0c;其中c不等于b。若a和c的最大公约数为…

MFC 错误 error C2504: “CDialogEx”: 未定义基类,以及错误error C1189

MFC 错误 error C2504、error C1189 error C2504: “CDialogEx”: 未定义基类-报错解决报错原因问题解决方法&#xff1a; ## 错误 error C1189 error C2504: “CDialogEx”: 未定义基类-报错解决 在MFC文件中添加资源窗口&#xff0c;后添加新类&#xff0c;随后在.h头文件中…

HDU2504 FLY

Problem Description 有三个正整数a,b,c(0<a,b,c<10^6)&#xff0c;其中c不等于b。若a和c的最大公约数为b&#xff0c;现已知a和b&#xff0c;求满足条件的最小的c。 Input 第一行输入一个n&#xff0c;表示有n组测试数据&#xff0c;接下来的n行&#xff0c;每行输入…

C++ 头文件的相互包含问题C2504未定义基类 | C2143,C4430,C2238

文件相互包含的错误问题 序言可能会有的疑问原因分析C2504: 未定义的基类C2143: 语法错误: 缺少“;”(在“*”的前面)C4430: 缺少类型说明符 - 假定为 int。注意: C 不支持默认 intC2238: 意外的标记位于“;”之前 解决方案 序言 文件相互包含的错误问题实际是两个类相互包含&…

HDU - 2504

有三个正整数a,b,c(0<a,b,c<10^6)&#xff0c;其中c不等于b。若a和c的最大公约数为b&#xff0c;现已知a和b&#xff0c;求满足条件的最小的c。 Input 第一行输入一个n&#xff0c;表示有n组测试数据&#xff0c;接下来的n行&#xff0c;每行输入两个正整数a,b。 Outpu…

error C2504 base class undefined

今天遇到的bug&#xff0c;觉得很诡异&#xff0c;明明引用了头文件却找不到基类定义&#xff0c;百度之后解决&#xff0c;觉得是个值得注意的地方&#xff0c;很细小&#xff0c;但是很难查~~~以后注意&#xff01;引以为戒。 之前写程序时&#xff0c;最喜欢把类的头文件全…