Hello codeforces, recently i solved this [problem](https://vjudge.net/problem/UVALive-3722).↵
↵
Generally speaking, given four integers `x,a,n,c`, `c` is a prime number.↵
↵
You are asked to calculate `f(n)%c`:↵
↵
↵
$$↵
f(0)=x\\↵
f(n)=a\cdot (f(n-1)-1)↵
$$↵
↵
which leads to:↵
↵
$$↵
f(n)=a^n\cdot x - (a+a^2+a^3+...+a^n)=a^n\cdot x-\frac{a\cdot (a^n-1)}{a-1}↵
$$↵
↵
The key part is the fraction part. At first, I try 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. AsI 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](https://vjudge.net/solution/21673582)↵
↵
Here is my AC submission: [submission_2](https://vjudge.net/solution/21674716)↵
↵
Thanks in advance.
↵
Generally speaking, given four integers `x,a,n,c`, `c` is a prime number.↵
↵
You are asked to calculate `f(n)%c`:↵
↵
↵
$$↵
f(0)=x\\↵
f(n)=a\cdot (f(n-1)-1)↵
$$↵
↵
which leads to:↵
↵
$$↵
f(n)=a^n\cdot x - (a+a^2+a^3+...+a^n)=a^n\cdot x-\frac{a\cdot (a^n-1)}{a-1}↵
$$↵
↵
The key part is the fraction part. At first, I try 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
↵
For clarity, here are my two submissions.↵
↵
Here is my WA submission: [submission_1](https://vjudge.net/solution/21673582)↵
↵
Here is my AC submission: [submission_2](https://vjudge.net/solution/21674716)↵
↵
Thanks in advance.
