HDU 2504 又见GCD(数论,最大公约数)

时间:2022-09-20 15:42:02

又见GCD

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 19497    Accepted Submission(s): 8129

Problem Description
有三个正整数a,b,c(0<a,b,c<10^6),其中c不等于b。若a和c的最大公约数为b,现已知a和b,求满足条件的最小的c。
 
Input
第一行输入一个n,表示有n组测试数据,接下来的n行,每行输入两个正整数a,b。
 
Output
输出对应的c,每组测试数据占一行。
 
Sample Input
2
6 2
12 4
 
Sample Output
4
8
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
int a;
int b;
int c;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&a,&b);
for(int i=2*b; i<=a; i++)//注意枚举范围2*b-a
{
if(gcd(i,a)==b)
{
printf("%d\n",i);
break;
}
}
}
return 0;
}

  

HDU 2504 又见GCD(数论,最大公约数)的更多相关文章

  1. HDOJ&lpar;HDU&rpar; 2504 又见GCD&lpar;利用最大公约数反推&rpar;

    Problem Description 有三个正整数a,b,c(0 import java.util.Scanner; public class Main{ public static void ma ...

  2. HDU 2504 又见GCD&lpar;最大公约数与最小公倍数变形题&rpar;

    又见GCD Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Subm ...

  3. HDU 2504 又见GCD

    又见GCD Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Subm ...

  4. HDU 2504 又见GCD (最大公因数&plus;暴力)

    题意:是中文题. 析:a和c的最大公因数是b,也就是说,a和c除了b就没有公因数了.再说就是互质了. 所以先把a除以b,然后一个暴力n,满足gcd(a, n) =1,就结束,就是n倍的c. 代码如下: ...

  5. HDU 2054 又见GCD

    又见GCD Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Subm ...

  6. HDU 2504&period;又见GCD-递归

    又见GCD Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submi ...

  7. 杭电2504 又见GCD

    又见GCD Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submi ...

  8. hdu 4983 Goffi and GCD&lpar;数论&rpar;

    题目链接:hdu 4983 Goffi and GCD 题目大意:求有多少对元组满足题目中的公式. 解题思路: n = 1或者k=2时:答案为1 k > 2时:答案为0(n≠1) k = 1时: ...

  9. &lbrack;Swust OJ 1125&rsqb;--又见GCD&lpar;数论,素数表存贮因子&rpar;

    题目链接:http://acm.swust.edu.cn/problem/1125/ Time limit(ms): 1000 Memory limit(kb): 65535   Descriptio ...

随机推荐

  1. android之location01

    <uses-permission android:name="android.permission.ACCESS_FINE_LOCATION"/> <Linear ...

  2. curl&lowbar;setopt函数相关应用及介绍&lpar;转&rpar;

    一.要想使用curl_setopt 这个函数必须在服务器里边进行编译curl这个组件,怎么安装编译这个组件请具体到google搜索 二.curl_setopt的php帮助文档的解释 bool curl ...

  3. 面试中关于Java中涉及到知识点(转)

    本篇文章会对面试中常遇到的Java技术点进行全面深入的总结,帮助我们在面试中更加得心应手,不参加面试的同学也能够借此机会梳理一下自己的知识体系,进行查漏补缺. 1. Java中的原始数据类型都有哪些, ...

  4. macos上安装wget命令

    首先从Apple Store下载Xcode,然后安装Xcode,接着安装Homebrew包管理,类似于Ubuntu下的apt-get: 终端下输入ruby -e "$(curl -fsSL ...

  5. Qt&&num;160&semi;Opencv&&num;160&semi;在Linux下摄像头简单示例(转)

    下面写的文章也许网上也有类似的,但是大多数都没有给出思路及背景,让初学者每次都只能学到一点皮毛,不少知识需要大量搜索零碎地拼凑起来.题外话,虽然现在是碎片化信息时代,但正是这样信息整合能力也显得非常重 ...

  6. 初探VUX&lpar;基本官网上无特别无干货&rpar;

    vux@2.x 推荐webpack+vue-loader方式的开发. 第一步安装cli依赖 npm install vue-cli -g 接下来创建项目注意名称是小写 cd projectPath y ...

  7. ORACLE更新数据时如果有就更新没有就插入

    SQL写法: begin update table_name set salary = 10000 where emp_id = 5; if sql%notfound then insert into ...

  8. Python3 configparse模块(配置)

    ConfigParser模块在python中是用来读取配置文件,配置文件的格式跟windows下的ini配置文件相似,可以包含一个或多个节(section),每个节可以有多个参数(键=值). 注意:在 ...

  9. JS学习笔记4&lowbar;BOM

    1.frame相关对象 top:指向最外层框架,使用top可以在一个框架中访问另一个框架,例如top.frames[index/name] parent:指向当前框架的直接上层框架 window:代码 ...

  10. linux shell 压缩解压命令

    .tar 解包:tar xvf FileName.tar打包:tar cvf FileName.tar DirName(注:tar是打包,不是压缩!)———————————————.gz解压1:gun ...