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

take modulus of x by 1e9+7 after scanning input.

Overflow most probably.

Maybe your program prints negative number?

if x==0 or x%1000000007==0:

This is wrong. Only if x==0 is required.

There is a chrome extension called CF-Predictor

Programming contest are half logics and half maths.

I think the main idea is that the maximum possible product is TOTALSUM*k, so there can be at most log_2(TOTALSUM*k) elements larger than 1 in a valid array.

Hence we can bruteforce over all possible (i,j) where i is the position of the first element larger than 1 in the array and j is the last position.

Once you have that you just need to look at how many extra ones you can add to the left of i and to the right of j.

I did this but I made a mistake I guess.

k = 0, I think.

i guess its y := 0

ans should be (x<<1)%M

Likely your program didn't pass that test case due to overflow. (That's what happened to me in the first attempt)

Darn. I missed ONE mod sign :(

it was x=0 i think;(

Just as n==2,n==3,n==4 and so on.

because at the end there will be twice the dresses, but there can be one less dress with 50% probability, so at the end there will be 2 * x and 2x + 1 dresses each with 50% prob. Rest is simple.

This gives f₀ = x

answer is twice of f_n

Just the 1st one

No, that it.

I did the same thing.

your code link ??

Because you solved it :D

Observe that after k months, there can be 2^k * x, 2^k * x - 1, ... , 2^k * x - (2^k - 1) clothes in the wardrobe, with equal probability .

By using definition of expected value, we find that the expected number of clothes after k months is . The answer to this problem is twice of this number, i.e. 2^k(2x - 1) + 1.

Note the special case: if x = 0, the answer is 0 no matter what k is.