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

Revision en2, by max_kibble, 2019-09-09 19:13:25

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 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)