제출 #332248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332248		DanerZein	Euklid (COCI20_euklid)	C++14	35 / 110	1060 ms	508 KiB

euklid

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
  if(b==0) return a;
  return gcd(b,a%b);
}
int R(int a,int b){
  if(b>a) swap(a,b);
  if(b==1) return a;
  if(a==1) return b;
  return R(a/b,b);
}
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t;
  cin>>t;
  while(t--){
    int g,h;
    cin>>g>>h;
    if(g==h){
      cout<<g<<" "<<h<<endl;
      continue;
    }
    if(h==2){
      cout<<g<<" "<<2*g<<endl;
      continue;
    }
    if(h*h==g){
      cout<<g<<" "<<h*g<<endl;
      continue;
    }
    bool sw=0;
    for(int i=1;i<=10000;i++){
      for(int j=1;j<=10000;j++){
	if(R(i,j)==h && g==gcd(i,j)){
	  cout<<i<<" "<<j<<endl;
	  sw=1;
	  break;
	}
      }
      if(sw) break;
    }
  }
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 40
• Subtask 6: 0 / 35