Split Sums - Editorial

Links:

Contest: Contest

Author: Ashish Ranjan
Editorialist:Ashish Ranjan

Difficulty Level:

Easy

PRE-REQUISITES:

Ad-Hoc,Maths

Explanation

Let S1 and S2 denote the set of marbles that A and B have.

It can be seen that sum(S1)+sum(S2)=n*(n+1)/2.(sum of first n natural numbers)
sum(S1)-sum(S2)=M.

So we know sum(S1) and sum(S2) from here.If sum(S1) and sum(S2) are integers,then we can split the first N natural numbers into two sets.

Now check if their GCD is 1 or not.If the GCD is 1,print Yes otherwise print No.

Simple python solution

can you please help me figure out whats wrong with this solution : https://www.codechef.com/viewsolution/17954766

write for the case where m>n i.e either of the sums is less than zero

What is wrong with my solution ?
i thought that Priority_sum_A +Priority_sum_B = N*(N+1)/2 and then Priority_sum_A - Priority_sum_B = M.Using this i got the value of Priority_sum_A = M+ Priority_sum_B and Priority_sum_B = ( N*(N+1)/2 - M)/2. So if Priority_sum_A and Priority_sum_B will have gcd==1 then “yes” else “no”.

import java.util.*;

public class Main {

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

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int T = sc.nextInt();
	while(T-- > 0){
		long n = sc.nextLong();
		long m = sc.nextLong();
		long sum = (n*(n+1))/2;
		
		if((sum+m) % 2 == 0){
			long a = (sum+m)/2;;
			long b = sum - a;
			if(gcd(a,b) == 1){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}				
		}else{
			System.out.println("No");
		}
		
	}

}

}