I am rui_er fan!

Unfortunately I can't participate, but GL&HF to you!

Hope to solve ABC in this round

As another problemsetter, Good Luck.

Div.2 will be as hard as Div.2, and Div.1 will be as hard as Div.1 :)

I think you will get upvoted if you mention the fact that you are also a team member of us.

Yeeeep

As a tester, I comment after purp4ever for a living.

when testing gets more upvotes than the actual contest

The sponsor is not available.

Clearly,this will make it more difficult to increase the rating.(

This is what I acknowledged from Algodoo marble races, so the figure above actually disobeys the rule in Algodoo.

Purple HSL: [270, 100, 100]

Violet HSL: [300, 100, 50]

And, more astonishing, violet belongs to Team Pink, not Team Purple. If we change "L" of violet to 100, we will obtain magenta, which definitely belongs to Team Pink.

Hope you can reach IGM! ^_^

Well, you did it oneesama~

++

wrong place ;[

wait no but same, had 4 penalties until I've figured it out

Brooo, thanks, completely missed that. There even was a hint that it's pre-test 3

it's not the Edu round bro

Maybe you can register Div.2 now and take part in Div.2.

Like changzhou, became Master but got negative delta in Div.2 :(

I think you have commented on the wrong blog.

Registration completed means u have successfully registered to participate in the contest, that doesn't mean that registration has ended for all.

Please comment in English or Russian.

because there's no sponsor :(

If you click on it, it will direct you to your profile :D

Going for D1 first before C might be a wise choice, because of its lower point value.

It mean task with subtasks. Example: Problem F in CF940

the rating will depend on updated rating of yesterday's contest.

i was stuck at C in yesterday's contest

I did in A.

are you angry now?

please comment in English or Russian

that problem of the ordered pairs(a,b) have the vibes of a N1 Imo Shortlist xd

what is MO?

Same mistake I did and suffered 2 WA.

k-=(mid-arr[i]); This will overflow. Since n is 1e5 and mid>=1e15

i got accepted on 2e17. (probably 1e18 is going overflow and others are not enough , dont know)

Yep, use BS to find max of min in the list after purchase.

you can BS what's the new minimum element after adding k cards

Probably possible, but not necessary. You can straight-up iterate one time to distribute evenly so that we have $$$x$$$ minimum elements ($$$x \le n$$$), then iterate another time if after that $$$k$$$ is still positive.

Yes, but not necessary. Wasted like an hour doing it. Then looked at implementation of top guys and felt really stupid.

My approach didn't even consider BS. Just get the list sorted and then bump up the minimum with your coins to equal the 2nd lowest, then the 3rd, etc.

nah it's just some basic math deductions lol, not sure if my solution will fst tho

It should be reduced to count pair $$$(a, b)$$$ such that $$$(a+b) | b^2$$$

You just need to prove that if $$$(a + b) | b^2$$$ then $$$(a+b) | gcd(a,b) b$$$

It's actually enough to iterate over all factors of $$$b^2$$$ that no more than $$$b+n$$$

Let $$$a=gx, b=gy$$$ where $$$gcd(x,y)=1, g=gcd(a,b)$$$. $$$(x+y)$$$ divides $$$gy$$$, let $$$gy=q(x+y)$$$ or $$$qx=y(g-q)$$$, $$$y$$$ divides $$$qx \implies y$$$ divides $$$q$$$. Let $$$q=py$$$. So $$$gy=pyx+py^2 \implies g=p(x+y) \implies p$$$ divides $$$g$$$. Also note that $$$x<n/g$$$ and $$$y<m/g$$$. This allows you to check all pairs $$$(x,y)$$$ such that $$$gcd(x,y)=1$$$ and $$$x+y = g/p$$$ by iterating through all values of $$$p,g$$$. Overall time complexity is $$$\sum_{p=1}^{min(m,n)} \sum_{g=rp, 1<=r<=min(m,n)/p} \ min(m,n)/(rp) = \sum_{p=1}^{min(m,n)} min(m,n)/p = O(min(m,n)log(min(m,n)))$$$

Here is how I solved B2

Assume that $$$gcd(a,b)=g$$$ and let $$$a=gx$$$,$$$b=gy$$$ and $$$gcd(x,y)=1$$$. Since we need $$$g(x+y)$$$ to divide $$$g^2y$$$, we get that $$$(x+y)$$$ divides $$$gy$$$. So let $$$A=x+y$$$ and $$$B=y$$$. Here are few observations

1. $$$A>B$$$

2. $$$gcd(A,B)=1$$$

3. $$$A$$$ divides $$$g$$$ giving $$$A\leq g$$$

4. $$$gB \leq m$$$

5. $$$g(A-B) \leq n$$$.

Thus we get that $$$B\leq\sqrt{m}$$$ and $$$A\leq \sqrt{m}+\sqrt{n}$$$. So we can brute force on each $$$(A,B)$$$ pair which satisfies $$$1$$$ and $$$2$$$ and find the value of $$$g$$$ that ensures $$$3$$$,$$$4$$$ and $$$5$$$ by say precomputing multiples of every number.

Maybe it is an easier way:

let $$$s=a+b$$$, then $$$(a+b)|b \cdot \gcd(a,b)$$$ equals to $$$s| b \cdot \gcd(b,s-b)$$$, equals to $$$s | b \cdot \gcd(b,s)$$$.

It meens that, for each prime $$$p$$$, let $$$p^{k_1}|b$$$ and let $$$p^{k_2}|s$$$, then $$$k_1 \ge k_2/2$$$.

Calculate all prime factors of all integers, for each $$$s$$$, calculate the number of $$$b$$$.

I solved it purely by observing the matrix. Took me a lot of time but managed to solve it using just prefix sums.

It is actually a tree with depth less than $$$\log n$$$.

Yes, the $$$i$$$-th value is actually $$$\binom{k+i}{i}$$$. If you turn your head, you should try see a pascal triangle

of cource 258890400

First, you have to see that a must be a multiple of b. Then, it is a pretty straightforward (n+m)*log(n+m) implementation, where you iterate over all possible b and over all multiples of b.

$$$a + b$$$ must clearly be a multiple of $$$b$$$. This is only satisfied when $$$a$$$ is a multiple of $$$b$$$.

However if $$$a$$$ is a multiple of $$$b$$$, then $$$gcd(a, b) = b$$$, meaning $$$a + b$$$ must actually be a multiple of $$$b ^ 2$$$.

So we have $$$a + b = k * b ^ 2$$$, or $$$a = k * b^2 - b$$$. So for each $$$b$$$, you can just count the number of multiples $$$k$$$ which generate valid values of $$$a$$$ in a total of $$$O(m \log m)$$$ or $$$O(m)$$$ time depending on implementation.

We are counting values of (a+b) which are multiples of b.gcd(a,b).

e.g. (a+b) = k.b.gcd(a,b) (for some k values)

dividing through b gives a/b + 1 = k.gcd(a,b)

This means that a is divisible by b, e.g. let a = Xb, then gcd(Xb, b) = b

Which reduces the problem to

a+b is divible by b^2

Iterate all b's, and look for how many b^2 fit beneath "maximum value of a" + the current b and sum them all up.

You need to know two things for this.

1) are you aware of "sieve of eratosthenes" ? What is the concept behind it ? What will be runtime complexity of it ?

2) Reduce the formula

=> (a + b) % (b * gcd(a,b)) = 0, 
=> (a + b) = k*(b * gcd(a , b) ) where 'k', is some random positive integer ( because 
=> Right side is divisible by 'b' . So, left side also must be divisible by 'b'. 
=> Left side, among (a + b) , 'b' is already divisible by 'b' ( obvious ) , so 'a' also must be divisible by 'b'. 

1. Based on above,  we know that 'a' is multiple of 'b'. 

Use two for loops, using sieve concept. complexity will be apprx O( n log n log n ) , considering modulo and division and multiplication occur in O(1).

Yeah being stuck in D2 made me lost rk1(Div 2). I spent almost an hour in it :(

Actually when you found that $$$x+y | g (xg=a, yg=b, g=(a,b))$$$, you will realize that $$$(x+y)g \le n+m$$$ and $$$x+y \le g$$$ which means that $$$x+y \le \sqrt{n+m}$$$, so you can brute force every possible (x,y) and solve the number of g in about $$$O(n+m)$$$.

BTW how to solve by Mobius Inversion I dont know lol