Hints:
Just catch the point that GCD of 3 consecutive numbers must be 1.
Solution:
If GCD of three consecutive numbers is 1,the first number cant be an even number because then the third number would obviously be an even number and so GCD wont be 1
example
2,3,4
when first number if even (2) third number will be even(4) and GCD wont be 1 here it is 2.
So the first number must be an odd number ex:3,4,5
Now comes the logic for three consecutive numbers only 2 can be a factor common to all three(if u cant figure out why feel free to comment or mail me,will reply ASAP)
so number of magoes = sum of numbers that satisfy the condition which in case is only the odd numbers
* Sum of odd numbers starting from 1 is n*n where n is the number of terms, here the number of terms is (N-1)/2
so number of mangoes is (N-1)/2*(N-1)/2
But we are required to give a number less than N so take modulo %
Here is the C code:
#include <stdio.h>
int main(void) {
long long int t,n,m;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
m = (n -1)/2;
m = m*m;
m = m %n;
printf("%lld\n",m);
}
return 0;
}
Just catch the point that GCD of 3 consecutive numbers must be 1.
Solution:
If GCD of three consecutive numbers is 1,the first number cant be an even number because then the third number would obviously be an even number and so GCD wont be 1
example
2,3,4
when first number if even (2) third number will be even(4) and GCD wont be 1 here it is 2.
So the first number must be an odd number ex:3,4,5
Now comes the logic for three consecutive numbers only 2 can be a factor common to all three(if u cant figure out why feel free to comment or mail me,will reply ASAP)
so number of magoes = sum of numbers that satisfy the condition which in case is only the odd numbers
* Sum of odd numbers starting from 1 is n*n where n is the number of terms, here the number of terms is (N-1)/2
so number of mangoes is (N-1)/2*(N-1)/2
But we are required to give a number less than N so take modulo %
Here is the C code:
#include <stdio.h>
int main(void) {
long long int t,n,m;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
m = (n -1)/2;
m = m*m;
m = m %n;
printf("%lld\n",m);
}
return 0;
}
How can u say the gcd of 3 numbers can be 2 ?
ReplyDeleteGcd of 3 consecutive numbers is always 1.
For even-odd-even or for odd-even-odd, 2 is never the gcd.
Yes of course GCD of three consecutive numbers is always 1.
DeleteBut what is asked in the question is "FOR EACH PAIR OF {M1,M2,M3} GCD SHOULD BE 1."
that means GCD(M1,M2)=1 GCD(M2,M3)=1 GCD(M1,M3)=1
so only if M1 and M3 are odd this will be true that is GCD{M1,M2,M3}=1
otherwise it is false. that is what @jayasurya says.
Am i correct Mr.Jayasurya??... -:)P
Nailed it bro (y)
DeleteWhat is the answer if n = 3?
ReplyDelete