Submission #332195

#	Time	Username	Problem	Language	Result	Execution time	Memory
332195		DanerZein	Euklid (COCI20_euklid)	C++14	19 / 110	1097 ms	492 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;
    }
    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: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 15 / 15
• Subtask 5: 0 / 40
• Subtask 6: 0 / 35