 # JCRYPTO - EDITORIAL

Contest

Setter: debrc

Tester: dustu_947 , mishra_roshan

Editorialist: debrc

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.