Sohsoh84's blog

By Sohsoh84, history, 4 months ago, In English

Hi :), I was solving 1228C - Простые числа и произведение, I found a solution for that during the virtual contest, but it failed on third sample testcase

I think that my solution is correct, anyway, if you found a bug inside my code or you think that my solution is totally wrong, please tell me inside the comments section :)

here is my solution:

lets set the initial value of $$$ans$$$ to 1

for each $$$p$$$ in prime divisors of $$$x$$$, let's iterate over all powers of $$$p$$$ witch are less than $$$n$$$ ($$$p^1$$$, $$$p^2$$$, $$$p^3$$$, ...), for each number like $$$k$$$ witch $$$p^k <= n$$$, let's count all numbers $$$y$$$ less than or equal $$$n$$$ where $$$g(y, p) = p^k$$$ and call this number $$$c$$$, and multiply the $$$ans$$$ with $$$(p^k)^c$$$

this is how we can calculate $$$c$$$: $$$\lfloor n / p^k \rfloor - \lfloor n / p^{k + 1} \rfloor $$$

this is my code:

Code

My answer for sample test3: 532291087

The real answer for sample test3: 593574252

and sorry for my bad English :)

Tags c++
 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it -17 Vote: I do not like it

you are candidate master and you don't know how to solve a problem with 1700 rating :|

»
4 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Figure it out yourself!

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

    I spend so much time to debug it, but I found nothing, so I asked for help(I have many unsolved problem that I had a try for them and I didn't found the problem In my solution, but this one differs, I really want to know why my solution is not correct)

»
4 months ago, # |
Rev. 3   Vote: I like it +40 Vote: I do not like it

Since your code works correctly on this sample with optimizations turned off, I've got a hypothesis:

The compiler assumes that the conditional if ((p * e) / e != p) (the one commented "preventing overflow") is always false. Why? Signed integer overflow is an example of undefined behavior, which cannot occur in a correct program, so the compiler is safe to assume it will never happen. Since it cannot happen, the equation $$$(p \cdot e) / e = p$$$ will always be true. This only happens during the program optimization process; when the optimizer is turned off, the translation of the program into the machine code is more verbatim.

In order to fix this, you either have to do your check on an unsigned data type, or write a check that cannot overflow.