Exciting Bets Codeforces Solution

Exciting Bets Solution

Welcome to Rockport City!

It is time for your first ever race in the game against Ronnie. To make the race interesting, you have bet aa dollars and Ronnie has bet bb dollars. But the fans seem to be disappointed. The excitement of the fans is given by gcd(a,b)gcd(a,b), where gcd(x,y)gcd(x,y) denotes the greatest common divisor (GCD) of integers xx and yy. To make the race more exciting, you can perform two types of operations:

See Also: Codeforces Round 730 (Div. 2)

  1. Increase both aa and bb by 11.
  2. Decrease both aa and bb by 11. This operation can only be performed if both aa and bb are greater than 00.

In one move, you can perform any one of these operations. You can perform arbitrary (possibly zero) number of moves. Determine the maximum excitement the fans can get and the minimum number of moves required to achieve it.

Note that gcd(x,0)=xgcd(x,0)=x for any x≥0x≥0.Input

The first line of input contains a single integer tt (1≤t≤5⋅1031≤t≤5⋅103) — the number of test cases.

The first and the only line of each test case contains two integers aa and bb (0≤a,b≤10180≤a,b≤1018).Output

For each test case, print a single line containing two integers.

If the fans can get infinite excitement, print 0 0.

Otherwise, the first integer must be the maximum excitement the fans can get, and the second integer must be the minimum number of moves required to achieve that excitement.ExampleinputCopy

8 5
1 2
4 4
3 9


3 1
1 0
0 0
6 3


For the first test case, you can apply the first operation 11 time to get a=9a=9 and b=6b=6. It can be shown that 33 is the maximum excitement possible.

For the second test case, no matter how many operations you apply, the fans will always have an excitement equal to 11. Since the initial excitement is also 11, you don’t need to apply any operation.

For the third case, the fans can get infinite excitement by applying the first operation an infinite amount of times.

For the fourth test case, you can apply the second operation 33 times to get a=0a=0 and b=6b=6. Since, gcd(0,6)=6gcd(0,6)=6, the fans will get an excitement of 66.


Program C++:

using namespace std;
typedef long long int ll;
#define int long long
#define pb push_back
#define mod 1000000007
#define setbits(x) __builtin_popcountll(x)
#define zerobits(x) __builtin_ctzll(x)
#define inf 1e18
#define pre(x,y) fixed<<setprecision(y)<<x
#define pq priority_queue<int>
#define mpq priority_queue<int,vector<int>,greater<int>>
#define gcd(x,y) __gcd(x,y)
#define mp make_pair

void solve()
    int n,a,b;
    if(a>b) swap(a,b);
    int g=gcd(a,b);
    if(a==b) cout<<0<<" "<<0<<endl;
    else if(g>=b-a) cout<<g<<" "<<0<<endl;
        int k=b/(b-a);
        cout<<(b-a)<<" "<<k<<endl;

int32_t main()
    int T;
	return 0;

Codeforces Round #730 (Div. 2)

Leave a Comment