HDU 2504

文章目錄

• • Problem Description
  • 題解：
  • 代碼：

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

題解：

單純的暴力就能過。。。。
也可以加點小優化，gcd(a,c)=b,那么gcd(a/b,c/b)=1,所以枚舉 i ,使得 i 滿足gcd（a/b,i）=1
反正怎么都能過

代碼：

#include<bits/stdc++.h> using namespace std; int gcd(int a,int b) {return b==0?a:gcd(b,a%b); } int main() {int a,b;int n;cin>>n;while(n--){cin>>a>>b;for(int i=b+1;;i++){if(gcd(a,i)==b){cout<<i<<endl;break;}}}return 0; }

總結

以上是生活随笔為你收集整理的HDU 2504 又见GCD的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。