Submission #473922

#	Time	Username	Problem	Language	Result	Execution time	Memory
473922		SaraMostafa	Euklid (COCI20_euklid)	C++14	35 / 110	1082 ms	312 KiB

euklid

#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long
#define endl "\n"
#define Sara ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const long long mod=1e9+7;
const double PI=acos(-1);
// 1 2 3 --> 1,2,3 ...1,2..1,3..1..2,3..2..3..none (2 power number of elements)
//1 2 3 --> 2--> 1,2..1,3..2,3..(!n/(r!(n-r)!)) aka:ncr
// 1 2 3 -->2-->1,2..2,1..1,3..3,1..2,3..3,2..(n!/(n-r)!) aka:npr
//1 2 3--> 1..1,2..1,2,3..2..2,3..3  number of subarrays -->(n*(n+1))/2 "sum of numbers from 1 to n."
/*
ll power(ll x,ll y)
{
    if(y==0)
        return 1;
    else if(y==1)
        return x%mod;
    ll  r=power(x%mod,((y%mod)/2)%mod);
    if(y%2==0)
        return ((r%mod)*(r%mod));
    else
        return ((r%mod)*(r%mod)*(x%mod));
}

ll inverse(ll md,ll x)
{
    return power(x%mod,mod-2);
}

*/
ll r(ll a,ll b)
{
    while(a>1 && b>1)
    {
        if(a<b)
            swap(a,b);
        a/=b;

    }
    if(a==1)
        return b;
    else
        return a;
}
int main()
{
    //freopen("input.in","r",stdin);

    Sara
    int t;
    cin>>t;
    while(t--)
    {
        ll h,g;
        cin>>g>>h;
        ll ans1=-1,ans2=-1;
        for(int i=1; i<=10000; i++)
        {
            ll a=g*i;
            for(int j=i; j<=10000; j++)
            {
                ll b=g*j;
                if(__gcd(a,b)==g && r(a,b)==h)
                {
                    ans1=a;
                    ans2=b;
                    break;
                }
            }
            if(ans1!=-1)
                break;
        }
        cout<<ans1<<' '<<ans2<<endl;
    }

    return 0;
}

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