logic of the question

general
, ,
1

https://www.codechef.com/NUCD2015/problems/NU01 Iam unable to understand the logic and how to approach of this question.will be oblighed.

1 Like
2

Source Code:

IT IS A SIMPLE PROBLEM CAN BE SOLVED BY SIMPLE MATHEMATICAL CONCEPTS. AND THE PROBLEM’S C CODE CAN BE WRITTEN LIKE THIS AS SHOWN UNDER:

#include (stdio.h)

#include (stdlib.h)

int cmp(const void *a,const void *b){

return *(int *)a-*(int *)b;

}

int main()

{

int m,temp,i,j;

int a[105];

scanf("%d",&m);


for(i=0;i<m;i++)

 scanf("%d",&a[i]);


qsort(a,m,sizeof(int),cmp);


for(i=2;i<=96000000;i++)

{

	temp=a[0]%i;

	for(j=1;j<m;j++)

	  if((a[j]%i)!=temp)

	     break;

	  if(j==m)

	  printf("%d ",i);

}
printf("\n");

 
return 0;

}

3

You’re supposed to find all integers ‘M’ such that array[i]%M is same for all elements in the array. When two numbers, say a,b have the same modulo with some other number ‘c’, then their absolute difference is divisible by ‘c’, for example, say, a=6,b=11 and c=5, then, a%c = b%c = 1 and also the absolute difference of a,b i.e., 11-6=5 is divisible by 5.

So our problem now becomes finding all possible ‘M’ such that the absolute difference of any pair of integers in the given array is divisible by ‘M’. So, we create a new array containing the absolute difference of every pair in the original array. Now we need to find all possible ‘M’ such that every number in this new array is divisible by ‘M’, the GCD of all the elements in the array is the largest of all such numbers and the rest are its factors.Take the sample case as an example:-

originalarray = {38,6,34}
newarray = {32,4,28} //(32=38-6,4=38-34,28=34-6)

the GCD of 32,4,28 is 4. The factors of 4 are 1,2,4 since the problem statement says that M > 1 we only print
2,4 as our answer.

1 Like