Submission #334636

#	Time	Username	Problem	Language	Result	Execution time	Memory
334636		achibasadzishvili	Euklid (COCI20_euklid)	C++14	110 / 110	39 ms	384 KiB

euklid

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll a,b;
ll edicul(ll x,ll y){
    if(y > x)swap(x , y);
    if(y == 1)return x;
    return edicul(x / y , y);
}
int main(){
    ios::sync_with_stdio(false);
    ll q;
    cin >> q;
    while(q--){
        cin >> a >> b;
        ll l = b,r = 2*b*b;
        while(r <= 1000000){
            l = l * b;
            r = r * b;
        }
        
        r--;
        while(r%a)r--;
        
        ll x = ((b * r - 1) / a + 1)* a;
        
        while(__gcd(x , r) != a)x += a;
        
        //cout << edicul(x , r) << '\n';
        cout << x << " " << r << '\n';
    }
    return 0;
}

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