Have a look at my "N independent " solution(except when a=b), of course it is wrong but it still passes . Test cases where it should have failed… some test cases :
there are many many more test cases where it should have failed. Test cases were very weak. I understand that making good test cases is difficult task but this time they are extremely weak.
Hello
GCD(A+B,|A-B|)=GCD(AA+BB,|A-B|)=GCD(AAA+BBB,|A-B|) and so on…;
therefore solution is GCD(A+B,|A-B|);
Can anyone explain me why my solution is giving tle and test cases where it fails
As mentioned by @khiljee and @bvsbrk in the above posts, I used the fact that
gcd(a^n + b^n, a-b) = gcd(2*b^n, a-b)
Use prime factorization to find GCD as below:
If we have the unique prime factorizations of a = p1^e1 p2^e2 ⋅⋅⋅ pm^em and b = p1^f1 p2^f2 ⋅⋅⋅ pm^fm* where ei ≥ 0 and fi ≥ 0, then the gcd of a and b is
gcd(a,b) = p1^min(e1,f1) * p2^min(e2,f2) * ⋅⋅⋅ pm^min(em,fm).
I was failing some test cases while using the prime factorization approach as above. Which I fixed while the competition approached its end.
The case being, we can compute primes for 2*b and a-b separately and extend the solution to know primes for 2b^n, and hence find GCD. If you use 2b to compute prime, say 2 happened x times in prime factorization of 2*b, while extending the solution 2*b^n we should raise power as (x-1)*n + 1 instead of x*n times.
My solution here
Can somebody tell me whats wrong in the following approach?
Let G be gcd(A^N+B^N, A-B) (assuming A > B)
We need to find G%M where M = 1e9+7.
G*X = A^N+B^N and G*Y = A-B take % on both sides
(G%M)*(X%M) = (A^N+B^N)%M and (G%M)*(Y%M) = (A-B)%M
Let G%M = G1, X%M = X1 and Y%M = Y1
G1*X1 = (A^N+B^N)%M
G1*Y1 = (A-B)%M
So from above two equations G1=G%M is gcd of (A^N+B^N)%M and (A-B)%M
Hi @shahanurag, your assumption can be invalidated using the following:
GCD(A % M, B % M) != GCD(A, B) % M
Try it out for A = 14, B = 24 and M = 5:
GCD(14 % 5, 24 % 5) != GCD(14, 24) % 5
GCD(4, 4) != GCD(2) % 5
4 != 2 // which is true
I too got stuck at this point! But the following holds true:
GCD(A, B) = GCD(B, A % B)
So, we can say that:
GCD(AN+BN, A-B) = GCD(A-B, (AN+BN)%(A-B))
Thus while calculating (AN+BN)%M take M=A-B
and the answer would be GCD(M, (AN+BN)%M) % 1e9+7
Here’s my solution
My solution was to notice that A - B is smaller than A ^ N + B ^ N. Then we can find all the factors of A - B, and for each one of them check whether or not that factor of A - B divides A ^ N + B ^ N and by taking the maximum of all of these numbers we find the gcd(A - B, A ^ N + B ^ N).
Time complexity - O(TMlog N), M = 10^6
Can’t we use:
long long d = (bpow(a, n, MOD) + bpow(b, n, MOD)) % (MOD);//MOD=10^9+7
instead of
long long d = (bpow(a, n, a - b) + bpow(b, n, a - b)) % (a - b);
Can anyone explain me the prod function in tester’s solution,
long long prod(long long a, long long b, long long mod = MOD)
{
long long res = 0;
while(b)
{
if(b & 1)
res = (res + a) % mod;
a = (a + a) % mod;
b >>= 1; // right shift
}
return res;
}
I see it is similar to fast exponentiation but I don’t really get this code
Can anyone please explain me why first code CodeChef: Practical coding for everyone gets TLE while the second one CodeChef: Practical coding for everyone doesn’t. The only difference between them is in loop condition. In first its (i*i)<=d while in second its i<=(d/i).
You are referring to tester’s solution.
We are using the following identity:
GCD(A^N+B^N,A-B)=GCD((A^N+B^N)mod(A-B),A-B).
Although the said solution does not output the result mod 10^9+7 which, I would think, it should.
Please fix this incomplete sentence - “The only property required to solve the complete problem is GCD(U,V)=GCD(U.”
There are discussions going in at least 2 of them - I cant delete them hence. I am seeing what can be done, if needed.
Thank you, for a few days, I was stuck at this idea trying to prove or invalidate it. Finally I scrapped it, and now it turns out it was wrong. Thanks for giving a fail case 
No problem mate. I’m glad that you found this helpful
This is incorrect. GCD(2+1, |2-1|) != GCD(2 * 2 + 1 * 1, |2-1|)
edited that @utkalsinha but I am not sure whether it will really be edited or not as discuss is facing some issues nowadays…
Thanks for the test cases.
The links to the solutions are a bit mixed up. Currently, the solution marked as author solution is actually using int128.