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 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).
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
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.
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
long long d = (bpow(a, n, a - b) + bpow(b, n, a - b)) % (a - b)
Here why are we taking mod with (a-b) instead of 1e9+7 because a-b can be as big as 1e12 which is causing overflow but 1e9+7 won’t cause overflow. I am not able to understand where I am wrong.