Hello codeforces, recently i solved this problem.
Generally speaking, given four integers x,a,n,c, c is a prime number.
You are asked to calculate f(n)%c:
which leads to:
The key part is the fraction part. At first, I tried to solve the problem with binary exponentiation and Fermat's little theorem. I noticed that in this problem a-1 could be times of c and took care of the condition in implementation. However, the submission is verdict as WA. Later, I tried another way to calculate the fraction and got accepted.
But I'm still puzzled about why Fermat's little theorem failed in this problem. As the online judge website didn't provide test cases, I randomly generated over 100,000 test cases. There are no differences between outputs of the two submissions.
For clarity, here are my two submissions.
Here is my WA submission: submission_1
Here is my AC submission: submission_2
Thanks in advance.
Conclusion
The input data of this problem is wrong, which contain test cases with c not a prime.
Auto comment: topic has been updated by max_kibble (previous revision, new revision, compare).
Sorry if I'm wrong, but shouldn't the formula be like:
$$$f(n) = (a^n* x) - (\dfrac{a^{n + 1} - 1}{a - 1} - 1) $$$
Your formula is equal to OP's.
There is no fail in Fermat's theorem. It's said that $$$p\ is\ prime\ AND\ a\ mod\ p\ !=\ 0\ => a^{p - 1} \equiv 1 (mod p)$$$.
As you said $$$a - 1$$$ can be dividable by $$$c$$$ so you just can't use there this theorem since conditions aren't satisfied.
You have fraction $$$\frac{a(a^n-1)}{a-1}$$$. You know this is integer number so if $$$a-1$$$ is dividable by $$$c$$$ then numerator is dividable by $$$c$$$ too. So in your WA solution fraction always calculated as zero. Of course there is countertest: $$$c = 3,\ a = 10,\ n = 1$$$. Fraction is equal to 10 and correct result must be 1 (10 mod 3 = 1).
I don't know easier way to calculate correct fraction then your binary summation.
Actually in my WA submission, I did not use Fermat's little theorem when $$$a-1$$$ is dividable by $$$c$$$. In such condition, $$$a\equiv 1\ (mod\ c)$$$. Thus I use the sum $$$a+a^2+...+a^n$$$ instead of the fraction. Here is what I did in my code:
// A is the ax^n part if ((a - 1) % c == 0) { assert(A == x % c); ans = A - n % c; }And what you trying to do there? Just assume that fraction is equal to $$$n$$$? That's not correct too. And assert can fail since $$$A = (x * a^n)\ mod\ c$$$ and this is not always equal to $$$x\ mod\ c$$$.
In my understanding, if $$$a\equiv 1\ (mod\ c)$$$:
$$$a+a^2+...+a^n\equiv 1+1+...+1\equiv n\ (mod\ c)$$$. And the fraction equals the summation.
Why does $$$x\cdot a^n\equiv x\ (mod\ c)$$$ fail when $$$a\equiv 1\ (mod\ c)$$$
You absolutely right
In short: as I see there is test where $$$c$$$ is not prime. That's why your second solution works: it relies only on multiplicative and summative operations which are independent of "module primality".
Auto comment: topic has been updated by max_kibble (previous revision, new revision, compare).
Auto comment: topic has been updated by max_kibble (previous revision, new revision, compare).
Probably $$$a < c$$$ doesn't hold. You can just use divide and conquer to calculate that sum.