HDOJ(HDU) 2504 又见GCD(利用最大公约数反推)

简介: HDOJ(HDU) 2504 又见GCD(利用最大公约数反推)

Problem Description

有三个正整数a,b,c(0

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int t =sc.nextInt();
        while(t-->0){
            int a =sc.nextInt();
            int b =sc.nextInt();
            int c=0;
            for(int i=2;;i++){
                if(goc(a,i*b,b)){
                    c=i*b;
                    break;
                }
            }
            System.out.println(c);
        }
    }
    //验证,a和c的最大公约数是不是b
    private static boolean goc(int a, int c, int b) {
        int n=a;
        int m=c;
        if(n<m){
            n=n^m;
            m=n^m;
            n=n^m;
        }
        while(m>0){
            int k=n%m;
            n=m;
            m=k;
        }
        if(n==b){
            return true;
        }
        return false;
    }
}
目录
相关文章
|
3月前
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
【刷题记录】最大公因数,最小公倍数(辗转相除法、欧几里得算法)
|
算法
HDOJ(HDU) 2503 a/b + c/d(最大公约数问题)
HDOJ(HDU) 2503 a/b + c/d(最大公约数问题)
131 0
|
Go
HDOJ/HDU 1133 Buy the Ticket(数论~卡特兰数~大数~)
HDOJ/HDU 1133 Buy the Ticket(数论~卡特兰数~大数~)
106 0
HDOJ/HDU 2561 第二小整数(水题~排序~)
HDOJ/HDU 2561 第二小整数(水题~排序~)
111 0
|
Java
HDOJ/HDU 5686 Problem B(斐波拉契+大数~)
HDOJ/HDU 5686 Problem B(斐波拉契+大数~)
99 0
|
测试技术
HDOJ(HDU) 1859 最小长方形(水题、、)
HDOJ(HDU) 1859 最小长方形(水题、、)
78 0
|
机器学习/深度学习
HDOJ(HDU) 2083 简易版之最短距离(中位数)
HDOJ(HDU) 2083 简易版之最短距离(中位数)
136 0