[UVALive-3722] Why does Fermat's little theorem fail?
Difference between en2 and en3, changed 70 character(s)
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 tr
yied 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://
vjudge.net/solution/21673582ideone.com/vgoLxz)↵

Here is my AC submission: [submission_2](https://
vjudge.net/solution/21674716ideone.com/CdoNLU)↵

Thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English max_kibble 2019-09-10 07:07:17 107
en3 English max_kibble 2019-09-10 05:31:46 70 Tiny change: 'irst, I try to solve ' -> 'irst, I tried to solve '
en2 English max_kibble 2019-09-09 19:13:25 2 Tiny change: 'oblem. As I the onlin' -> 'oblem. As the onlin'
en1 English max_kibble 2019-09-09 19:10:40 1251 Initial revision (published)