GCD Plus LCM

In this problem you will be given two integers a, b. You have to answer if GCD(a,b)+LCM(a,b)=a+b is …

Click here to read the complete problem statement.


If you need help solving this problem, mention your approach and ask specific questions. Please avoid sharing your code and asking the Community to figure out “what’s wrong”.

#include<bits/stdc++.h>
using namespace std;

unsigned long long gcd(unsigned long long a, unsigned long long b)
{
    if(a==0) return b;
    return gcd(b%a, a);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    unsigned long long a, b, c, lcm, t;
    cin>>t;
    while(t>0) {
        cin>>a>>b;
        c = gcd(a, b);
        lcm = (a*b)/c;
        if((c+lcm) == (a+b)) cout<<"true\n";
        else cout<<"false\n";
        t--;
    }

    return 0;
}

I am getting WA for that in 2nd test case…
Please help…

The problem might be integer overflow,

assume,

a = 10 ^ 18
b = 10 ^ 18

That means,

a * b = (10 ^ 18) * (10 ^ 18) = 10 ^ (18 + 18) = 10 ^ 36

and 10 ^ 36 is of course out of the limit of unsigned long long.

I think this is the reason of WA.

And, @hjr265, can’t solve this with python3. Can you fix the time limit?

#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n,i,a,b;
cin>>n;
for(i=0; i<n; i++){
cin>>a>>b;
if(b%a==0 || a%b==0)
cout<<“true”<<endl;
else
cout<<“false”<<endl;
}
return 0;
I am getting cpu limite ex in 6 test plz help

Try to use scanf and printf instead of using cin and cout.

#include<bits/stdc++.h>
using namespace std;

int gcd(int a, int b){

while(b>0){
	int temp=b;
	b=a%b;
	a=temp;
}
return a;

}

int lcm(int a, int b){

return a*(b/gcd(a,b));

}

int main(){

int t;
	cin>>t;

while(t--){
	
	int a,b;
		cin>>a >>b;
	int temp=gcd(a,b)+lcm(a,b);
	int sum=a+b;
	if( temp == sum)
		cout<< "true" <<endl;
	else
		cout<<"false" <<endl;
}
return 0;

}

Whats the problem in this code???
Please help

Why TLE @hjr265 ??? I haven’t even used a loop!

#include <bits/stdc++.h>

using namespace std;

int main() {
	long long int t;
	cin>>t;
	while(t--){
		long long int a,b;
		cin>>a>>b;
		if(b%a == 0 || a%b==0) cout<<"true"<<endl;
		else cout<<"false"<<endl;
	}
	return 0;
}

Here is the submission: https://toph.co/s/679603

Edit: I have got AC. But why by using printf() and scanf() I have got AC while I got TLE by using cout and cin!!

Possible because of this: Faster I/O | Toph Tutorials

Although, if that really is the case, then the problem statement should have a warning about it. I will check and update the statement.

#include <stdio.h>
unsigned long long int gcd_(unsigned long long int a, unsigned long long int b)
{
    unsigned long long int c=a%b;
    if(c==0)
        return b;
    return gcd_(b, c);
}
int main() {
	int t=0,i=0,j=0;
	unsigned long long a,b, lcm, gcd, max, sum1=0, sum2=0;
	scanf("%d", &t);
	for(i =0; i < t; i++){
		scanf("%lld%lld",&a,&b);
		a = ( a > 0) ? a : -a;
	    b = ( b > 0) ? b : -b;
		if(a>b){
		max = a;
			gcd = gcd_(b,max);
			//printf("GCD : %d", gcd);
		}else{
			max = b;
			gcd = gcd_(a,max);
			//printf("GCD: %d", gcd);
		}
		
		lcm = (a*b)/gcd;
			//printf("\nLCM: %d", lcm);
		sum1 = lcm + gcd;
			//printf("\nLCM + GCD : %d\n", sum1);
		sum2 = a+b;
		if(sum1 == sum2){
			printf("true\n");
		}else{
			printf("false\n");
		}
	}
	return 0;
}

why i am getting WA in second test case?