Спасибо за участие!

1744A - Number Replacement придумал MikeMirzayanov, подготовил 74TrAkToR

1744B - Even-Odd Increments придумал и подготовил 74TrAkToR

1744C - Traffic Light придумали MikeMirzayanov и 74TrAkToR, подготовил 74TrAkToR

1744D - Divisibility by 2^n придумал и подготовил 74TrAkToR

1744E2 - Divisible Numbers (hard version) придумал и подготовил 74TrAkToR

1744F - MEX vs MED придумал и подготовил 74TrAkToR

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Nice Editorial, and very nice round!

This is so sad. If I knew that the max number of divisors in a number < 1e9 is 1344 I for sure could have finished question E2 because I had the same idea is the editorial. :(((

I didn't knew that but the solution made sense and I didn't have any other idea so I just assumed it. If it would have failed, it would have failed. What I'm saying is sometimes you have to go with your gut instead of proving whether the solution will work. Atleast that's what I think.

That is true but I didn't really have any gut feeling that told me that the max number of divisors would be small. In fact my gut actually told me that the number of divisors of sum n could be as big as a constant fraction of sqrt(n). But ig i should have tried it anyways.

Things like these have happened to me also. In these situations, may be we should refer OEIS and try to get some idea. OEIS does help in such mathematical problems.

Maximal number of divisors of any n-digit number.

You can argue that the logic wouldnt TLE without knowing the exact number as 1344. Since the number of divisors of

`n = 2^a 3^b 5^c ...`

is given by`(a+1)*(b+1)*(c+1)...`

, we can get a very rough estimate for the upper bound of the number of divisors asWait I don't understand your logic for calculating upper bound of max number of divisors. Also 1e5 is too big for an n^2 algorithm isn't it?

`Since x⋅y must be divisible by a⋅b, the following conclusion can be drawn: y must be divisible by a⋅b/gcd(a⋅b,x)`

Can anyone please prove this how in the problem E.

This is not something that you "prove". It is something that you intuitively know. When you unpack this statement it doesn't actually say much but the math makes it kind of convoluted so I'll explain it. To have some x*y be divisible by a*b, the set of prime divisors in a*b should be a subset of prime divisors in x*y. In other words, for every prime divisor in a*b, that prime divisor should also exist in x*y. Now if you think about it, gcd(a*b, x) simply means the set of prime divisors in x, which are also prime divisors in a*b. This means that the y that you choose only has to contain the prime divisors that is in a*b but not in x. This is given by the expression u gave ((x*y)/gcd(a*b, x)).

Had same doubt.Thanks for explaining.

how does it mean that gcd(a*b , x) means the set of prime divisors of which are also prime divisors in a*b

What a clear explanation

The Editorial didn't add to Contest materials and lots of ppl don't know that it comes

Nice Editorial,thanks.

Anyone know how so many solution for E were being hacked? What did the test case contain?

Some please explain F

Can anyone please explain why this code is not working? This is the code for Problem D.

178113368

Hi, your solution is almost correct... When choosing which indices to apply the operation on, you went from N to 1, but a bigger number doesn't necessarily mean a bigger number of twos. Take for example 5(0) and 4(2). So instead of going from N to 1, you should sort the indices by their number of twos and go from the biggest to the smallest. Hope this helps <3

I have a better time complexity solution for E, which works in

`O(sqrt(a) + 1344 * log(1344))`

.I have no idea why this works. Can somebody please help? https://mirror.codeforces.com/contest/1744/submission/186708442

The code iterates through all factors of a (say p) and finds the largest factor of b (say q) such that x = a * q / p and y = b * p / q. Then it takes the multiple of x just smaller or equal to c and the same for y. The code then swaps the numbers and does it again.

2333 But I'm a Chinese primary student.