max_kibble's blog

[UVALive-3722] Why does Fermat's little theorem fail?
By max_kibble, history, 5 years ago, In English

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

Here is my AC submission: submission_2

Thanks in advance.

Conclusion

The input data of this problem is wrong, which contain test cases with c not a prime.

Full text and comments »

  • Vote: I like it
  • +21
  • Vote: I do not like it