Polyn0mial's blog

By Polyn0mial, history, 2 years ago, In English

I was solving this problem. The formula for this problem can be founded here. I've stress tested my code, and found out that this is the smallest test case where my code failed (answer for n <= 225537 are all correct).

Input
Output
Expect

It is obvious that my output is wrong, since $$$answer(n) > answer(n-1)$$$. I have no idea why my code doesn't work.

Code
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think phi_pref is overflowing

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you! I somehow thought that I'm doing prefix sums on mobius and use int instead of long long since mobius only has -1, 0, 1 and won't overflow.