### 74TrAkToR's blog

By 74TrAkToR, history, 18 months ago,

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

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

• +52

| Write comment?
 » 18 months ago, # |   +3 Nice Editorial, and very nice round!
 » 18 months ago, # |   0 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. :(((
•  » » 18 months ago, # ^ |   0 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.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 18 months ago, # ^ |   0 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 as max divisors = (log_2(10^9)+1) * (log_3(10^9)+1) * (log_5(10^9)+1) * ... = 33 * 20 * 13 * 9 * ... < 10^5 
•  » » » 18 months ago, # ^ |   +1 Wait 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?
 » 18 months ago, # |   0 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.
•  » » 18 months ago, # ^ |   0 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)).
•  » » » 14 months ago, # ^ |   0 Had same doubt.Thanks for explaining.
•  » » » 8 months ago, # ^ |   0 how does it mean that gcd(a*b , x) means the set of prime divisors of which are also prime divisors in a*b
•  » » 18 months ago, # ^ |   0 Both x and y should together make up a*b => so x should have some part of a and some part of b. => so y should have some part of a and some part of b.  This some part which is I mentioned above is nothing but "factor of a given number" Now x and y can be written as x = afact1 * bfact1 * k y = afact2 * bfact2 * k  Here k is some constant, afact1 and afact2 is factorials of a, bfact1 and bfact2 are factorials of b and also note that a = afact1 * afact2 = a, b = bfact1*bfact2  so fix afact1 and bfact1 we get afact2 = a/afact1 and bfact2 = b/bfact1 
•  » » » 18 months ago, # ^ |   0 What a clear explanation
 » 18 months ago, # |   0 The Editorial didn't add to Contest materials and lots of ppl don't know that it comes
 » 18 months ago, # |   0 Nice Editorial,thanks.
 » 18 months ago, # |   0 Anyone know how so many solution for E were being hacked? What did the test case contain?
 » 18 months ago, # |   +1 Some please explain F
 » 18 months ago, # | ← Rev. 2 →   0 Can anyone please explain why this code is not working? This is the code for Problem D.178113368
•  » » 18 months ago, # ^ |   0 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
 » 16 months ago, # |   0 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/186708442The 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.
 » 8 months ago, # |   0 2333 But I'm a Chinese primary student.