Happy Birthday rotavirus in advance.

Not rated for division 1.

is that true ??

any one mention KAN and MikeMirzayanov will have upVotes ?

KAN & MikeMirzayanov

It will probably be announced before the contest

just saw your graph! You have my respect, mate!

Of course, it will be announced before the contest. I'm sorry, I forgot to write it in the English announcement.

Do you ever get upvotes ? xD

creates confusion for non followers and boring too

Просто теперь все считают что первый див начинается с рейтинга 2100))

Your wish came true :)

Updated. Check now.

You should ask questions on "problems" page. There you can get answer momentarily.

If the answer is A, you should print the remainder of division of A on 10⁹ + 7.

:D :D

There are two numbers. Obviously, since gcd is x, therefore common factor is x. so now both have factor x. So first number is in form a*x and second is in b*x and gcd(a, b) must be equal to 1. Since both number can't have other than x. Now GCD* LCM = first_number * second number. So x*y = (x*a) * (b*x) So y/x = a*b so we need to find all pairs (a, b) where gcd(a, b) ==1 && min(a*x, b*x)>=l && max(a*x, b*x)<=r and damn this count is the answer. There is just one catch, that y must be divisible by x. Otherwise the answer will be 0.

If y is not divisible by x, answer is 0. Otherwise, all pair (a, b) that satisfy the condition can be represented by (x * a', x * b'). Let , , . Now the problem is counting number of pair (a', b') in range [l', r'] such that GCD(a', b') = 1 and LCM(a', b') = y'.

This can be done by iterate over all divisor d of y' and check if pair satisfy all the condition above.

My implementation

There are two numbers. Obviously, since gcd is x, therefore common factor is x. so now both have factor x. So first number is in form a*x and second is in b*y and gcd(a, b) must be equal to 1. Since both number can't have other than x. Now GCD* LCM = first_number * second number. So x*y = (x*a) * (b*x) So y/x = a*b so we need to find all pairs (a, b) where gcd(a, b) ==1 && min(a*x, b*x)>=l && max(a*x, b*x)<=r and damn this count is the answer. There is just one catch, that y must be divisible by x. Otherwise the answer will be 0.

1. Find the prime factors of y/x
2. For those prime factors which are present more than once, replace them with their product. For example: 12 = 2*2*2*3*5*5 should be made 12 = 3*8*125. Store these in a vector, say, "facts".
3. It can be noted that size of vector "facts" is not more 15. So we can iterate on all subsets of facts to multiply each value of facts to either a or b. (a and b are numbers to be found). This can be done using bitmasks. For calculated values of a and b, check if they are between l and r, and increment the ans variable.
4. Check specially for case when y is not divisible by x, and the case when a=b. Here is my solution 39374707

Simple Explanation is as follows:
LCM(a, b) = a * b / GCD(a,b) ....... eq(1)
and if g = GCD(a, b) you can write a = p * g ; b = q * g such that p & q are coprime i.e. GCD(p, q) = 1
So above equation 1 can be rewritten as
LCM(a, b) = ((p * g)*(q * g))/g
LCM(a, b) = p * q * g ; where g is gcd(a,b)
So now problem became: for given integers y and r , count number of unordered pair (p,q) such that y = p * q * r and p & q are coprime i.e gcd(p, q) = 1.
That you can do in O(sqrt(N))
Ref Solution

I thought of Divide & Conquer based solution but couldn't merge efficiently.

If somebody solved like this, then please help how!

Notice that the product will get big really fast. So for each starting index you can just iterate over the end index until the product gets too big (e.g.  > 2·10¹⁸). This will have runtime .

The only problem with this approach is that this doesn't hold if there are a lot of 1s in it. But you can modify the approach from above so that you jump over the 1s, and check in O(1) if there is a solution (there can be only one) with the 1s that you jumped over..

Couldn't code it in the time I had, but my idea was something like this:

I stored the sum upto n numbers in an array, and the value of k for the first n numbers taken consecutively in another array k[n]. Now, for every element for which k[i]>=k(required), just check if there are consecutive numbers up back till the last element with this property.

I've compressed segments, that contains only "1". Then you can just bruteforce all segments ([0; 0], [0; 1], ... [0; n-1], [1; 1], [1; 2], ...), refreshing p and s for O(1) and breaking when p>z, where z=(2*10^5)*(10^8)*(10^5).

It's working for O(n*log(z)), but you must handle overwflows carefuly.

You should check the case 1 1 1 1

It cost me 3 WAs as well :(

Edit: Answer for this case is 1 BTW, it gave me 2 due to an error in my code only for this specific case.

You wrote in the program:

int lcm(int a, int b)
{
    return (a*b)/gcd(a, b);
}

If a and b are too big, it can be overflow (10⁹·10⁹ = 10¹⁸ >  maximum value of int).

For example:

• test case: 1000000000 1000000000 1000000000 1000000000

• correct answer: 1

• your output: 0

I tried a sqrt approach, it was TLE 13. I was using unordered_maps, so I tried to implement hashes, but didn't finished in time. I think there is a log solution

Of course, No :)

Idea is simple, there are not many positions that greater than sum of previous.

Hey My square root decomposition solution 39389380 passed after contest. (missed submitting during contest by 1 minute). Have a look.

You were trying to reach new record on Codeforses or you just like the number 228? (Or it's the result of competition between two brothers?).

Overflow