hdu 2504 又见gcd-程序员宅基地

技术标签： Math

#include <iostream>
#include <algorithm>
using namespace std;

//  (a,c)=b  已知a,b求最小c (c!=b) 
//  a=bp c=bq   (p,q)=1 反证法 ：若 (p,q)=x(x>1) 则 p=xp' q=xq' -> a=bxp' c=bxq'  a,c最大公约数为 bx(x>1) bx>b 与已知b是最大公约数矛盾 所以 (p,q)=1 
// 为了使 c最小 c=bq  找到q最小&&(p,q)=1的q即可 


int gcd(int a,int b)
{
	if(a%b==0)
	{
		return b; 
	}
	else
	{
		return gcd(b,a%b);
	}
}

int main()
{
	int cas,a,b,c,p,q;;
	cin>>cas;
	while(cas--)
	{
		cin>>a>>b;
		p=a/b;
		q=2;// c!=b
		while(1)
		{
			if(gcd(p,q)==1)
			{
				cout<<b*q<<endl;
				break;
			}
			q++;
		}
	}
	return 0;
}

本文链接：https://blog.csdn.net/Jeremy1149/article/details/51706909

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

linux服务器开发(日志部分)snprintf()_linux snprintf-程序员宅基地

文章浏览阅读478次。buf:接收数据的缓冲区；size:接收数据的大小；format:如%d%s等，指定输出数据的格式…: 输出到缓冲区中的数据返回值：失败返回负数，返回输入数据的总字节数。_linux snprintf

element-ui中label过长换行与el-input等高_el-form-item中label文字超长-程序员宅基地

文章浏览阅读5k次，点赞5次，收藏18次。1. template中设置label:label = "'....\n....'"注意：双引号中需要添加单引号将内容包裹，然后在换行处添加'\n'2.css样式换行显示_el-form-item中label文字超长

如何调用API获取你想要的数据_labview调用api-程序员宅基地

文章浏览阅读673次。在现代软件开发中，API（应用程序编程接口）已经成为了连接不同系统和服务的桥梁。通过调用API，我们可以从各种数据源中获取所需的数据，并将其集成到我们的应用程序中。本文将介绍如何调用API获取你想要的数据，并提供详细的代码示例。_labview调用api

OpenMetadata本地开发环境搭建-程序员宅基地

文章浏览阅读2.8k次，点赞24次，收藏28次。OpenMetadata本地开发环境搭建_openmetadata

link linux-程序员宅基地

文章浏览阅读56次。http://www.cnblogs.com/peida/tag/每日一linux命令/http://jingyan.baidu.com/article/48206aeaf07f37216ad6b3a6.html转载于:https://www.cnblogs.com/jerry-wang-12/p/4675104.html_linuxlink4965agn驱动

Linux服务器下Java环境配置-详细_简述linux下配java环境,列出详细步骤和命令-程序员宅基地

文章浏览阅读3.2k次，点赞2次，收藏7次。环境：Linux环境具体步骤：1、首先查看当前服务器环境是否已配置了JAVA/命令：java -version2、开始配置① 通过官网下载JDK文件，地址：https://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html（此次安装的是jdk1.8.0_321）② 准备安装：在服务器根目录 /usr/local/ 下新增JAVA文件夹：mkdir java 将已下载的JDK_简述linux下配java环境,列出详细步骤和命令