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 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](https://ideone.com/vgoLxz)↵
↵
Here is my AC submission: [submission_2](https://ideone.com/CdoNLU)↵
↵
Thanks in advance.↵
↵
### Conclusion↵
The input data of this problem is wrong, which contain test cases with `c` not a prime.
↵
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 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](https://ideone.com/vgoLxz)↵
↵
Here is my AC submission: [submission_2](https://ideone.com/CdoNLU)↵
↵
Thanks in advance.↵
↵
### Conclusion↵
The input data of this problem is wrong, which contain test cases with `c` not a prime.
