CHFGCD - Editorial

Some test cases to consider:

Input

3
1 3
1 5
9 6

Expected Output

2
2
0

Your Output

1
1
1
2 Likes

It fails for the test input:

1
3 3

(and likely others).

Thanks. In this case GDC is already > 1.

you need to check gcd(x,y) first for 0 operation case, not just both even only

There exist case that both a,b are odd but you only need 1 operation. e.g. 15,19

1 ops on 17 and 1 ops on 29 resulting in 18 and 30 which have 2 as gcd

I was trying pretty little the same approach but was not able to get AC. Can anyone tell me why this code is wrong?

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

void solve()
{
ll x,y;
cin>>x>>y;
ll ans=0;
if((x%2==0) and (y%2==0))
cout<<0<<"\n";
else if(((x%2==0) and (y%2==1)) or ((x%2==1) and (y%2==0)))
cout<<1<<"\n";
else
cout<<2<<"\n";
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;cin>>t;
while(t–)
{
solve();
}
return 0;
}

2 Likes

Yeah yeah sorry…my bad thanks btw

1 Like