JCRYPTO - EDITORIAL

[debrc]

PROBLEM LINK:

Contest

Setter: debrc

Tester: dustu_947 , mishra_roshan

Editorialist: debrc

DIFFICULTY:

Simple

PREREQUISITES:

Basic observations, GCD.

PROBLEM:

Given two numbers M_1 and M_2, which is formed using two prime numbers P and S such that:
M_1 = P_1 * S
M_2 = P_2 * S
Find P_1 and P_2.

QUICK EXPLANATION

GCD of M_1 and M_2 will give S.
P_1 = M_1 / GCD(M_1 , M_2)
P_2 = M_2 / GCD(M_1 , M_2)

EXPLANATION

GCD of multiple numbers which is formed by multiplication of a random prime number P and a constant prime number S, will always yield in S.
From there, you can easily find out P for all the numbers.

TIME COMPLEXITY

Time complexity is O(log(min(M_1, M_2)) for finding GCD.

SOLUTIONS:

Setter's Solution

C++

#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define  MOD 1000000007
#define ll long long
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#include <bits/stdc++.h>
using namespace std;

void solve()
{
    ll m1,m2;
    cin>>m1>>m2;
    ll s=__gcd(m1, m2);
    ll p1,p2;
    p1=m1/s;
    p2=m2/s;
    cout<<p1<<" "<<p2<<endl;
}

int main()
{
    fio
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Python

import math
t=int(input())
for i in range(t):
    a,b=map(int, input().split())
    s=math.gcd(a,b)
    print(a//s,b//s)

Tester's Solution

C++

#include <iostream>
using namespace std;

long long gcd(long long a, long long b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
     
}


int main() {
	int T;
	std::cin >> T;
	while(T--)
	{
	    long long M1,M2;
	    long long P1,P2,S;
	    cin>>M1>>M2;
	    S=gcd(M1,M2);
	    P1=M1/S;
	    P2=M2/S;
	    std::cout << P1 <<" "<<P2<< std::endl;
	}
	return 0;
}

Java

import java.util.*;
 class Dcoder
 {
   static long gcd(long a,long b){
     if(b==0)
       return a;
      return gcd(b,a%b);
   }
   public static void main(String args[])
   { 
    Scanner  sc=new Scanner(System.in);
    
    int t=sc.nextInt();
    while(t-->0)  { 
      
      long m1=sc.nextLong();
      
       long m2=sc.nextLong();
       long s=gcd(m1,m2);
       System.out.println((m1/s)+" "+(m2/s));       
      } 
       }
 }

---

Feel free to Share your approach.
Suggestions are welcomed as always had been.