[UVALive-3722] Why does Fermat's little theorem fail?

Revision en1, by max_kibble, 2019-09-09 19:10:40

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:

$$$ 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 I 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.

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)