Problem 922C — Cave Painting Explanation

Правка en4, от alshahreyaj, 2018-05-20 17:45:04

A lot of people solve this problem. I see a lot of them didn't understand why this solution works. I also start finding to understand the solution. I read editorial, but i didn't understand. May be i'm not capable of it. But I tried to explain it in my way. Hope it will help a few beginner like me. Here is my explanation.

As, the problem said that if it is possible to get different reminder from 1 to k for a value n then print "Yes". As, the reminders have to be different, so we will get k different reminder. So, the reminders must have to be 0 to k-1. And their form are given below:

Reminder for k=k-1 (Other not possible. Because if the reminder is k-2 for k there couldn't be possible to have more k-1 reminder. So it must have to be k-1).

Reminder for k-1=k-2.

Reminder for k-2=k-3.

.

.

.

Reminder for 2=1.

Reminder for 1=0.

Now look, if we add now 1 with n, n will be divisible by all of the number from 1 to k. Because the reminders are only one less from the number, so if we add one with n, reminder for all will be zero. So, (n+1) must have to be a number which is divisible by all number from 1 to k. And, that's the LCM of 1 to k. Now, if we calculate, for k=42 the LCM of 1 to 42 is bigger than 10^18. So, there is no value of n possible n<=10^18 where k>42. Now, it's easy to calculate.

So, that's the explanation. Hopefully it will help who didn't understand the solution.

my solution: Here

Теги #number theory, lcm, cave painting, 922c

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский alshahreyaj 2018-05-20 17:48:33 0 (published)
en6 Английский alshahreyaj 2018-05-20 17:46:37 26
en5 Английский alshahreyaj 2018-05-20 17:45:42 8 Tiny change: 'k-2=k-3.\n\n.\n\n.\n\n.\n\nReminder' -> 'k-2=k-3.\n.\n.\n.\nReminder'
en4 Английский alshahreyaj 2018-05-20 17:45:04 21
en3 Английский alshahreyaj 2018-05-20 17:44:23 26
en2 Английский alshahreyaj 2018-05-20 17:43:02 2 Tiny change: '.\n[cut]\nNow look' -> '.\n[cut]\n\nNow look'
en1 Английский alshahreyaj 2018-05-20 17:41:54 1561 Initial revision (saved to drafts)