double-or-divide-1

Omar loves problem solving very much and today he faces the following problem. 

Given a multiset A of N integers {a_1, a_2, \ldots, a_N} and an integer L, his task is to perform L operations indexed from 1 to L in the ascending order of their indices.

Let's consider the operation with index i. Moreover, for i > 1, let p_{max} be a prime number in prime factorization of i with the greatest exponent in the factorization. If there are multiple primes with the greatest exponent in prime factorization of i, let p_{max} be the smallest one among them. The operation with index i is beneficial if and only if i = 1 or the remainder of division p_{max} by i is odd. Otherwise the operation is harmful. 

For example, operation with index i = 2 is harmful, because p_{max} \bmod i = 2 \bmod 2 = 0 which is even. On the other hand, operation with index i = 9 is beneficial, because p_{max} \bmod i = 3 \bmod 9 = 3 which is odd.

Omar must perform all L operations in ascending order of their indices. For each beneficial operation, he has to choose an integer from A and double its value. On the other hand, for each harmful operation, he has to choose an integer from A and divide its value by 2 using integer division. If during any operation any element of A becomes 0, then he removes this element from A. In addition, once A becomes empty, it is not affected by any future operations. In order for the problem to be a challenging one, the task is to maximize the sum of elements in A after performing all the operations.

Since Omar is not familiar with any math, he asks you for help in solving the problem.

Input:

In the first line of the input there are two space separated integers N and L denoting the size of the multiset A and the number of operations to perform. In the second line, there are N space separated integers denoting the elements of A.

Output:

In the first line, print a single integer K denoting the size of multiset A after all operations are performed.
In the second line, print exactly K space separated integers denoting the elements of A after all operations are performed. Print them in the non-decreasing order of their values. Since these values can be very large, print each value taken modulo 10^9+7 (Notice that this modulo operation is applied when the order of these elements is determined and it does not affect this order).

Constraints:

1 ≤ N, L ≤ 5 \cdot 10 ^ 5
1 ≤ a_i ≤ 10 ^ 6     

SAMPLE INPUT
5 4
2 4 5 8 10

SAMPLE OUTPUT
4
2 5 8 20

Explanation

In First Case:  

For Operations from index 1 to 4.  

For index = 1 , we will choose 10 and double it. The array changes to  2 , 4, 5, 8, 20.
For index = 2 , we will choose 2 and make it half. The array changes to  1 , 4, 5, 8, 20.
For index = 3, we will choose 1 and make it half.  The array changes to   4, 5, 8, 20.
For index = 4 , we will choose 4 and make it half. The array changes to  2 , 5, 8, 20.

Source: hackerearth | Difficulty: EASY
Tags: Number theory

Data structures

Greedy algorithms


Solutions:
from sys import stdin
import math
n,l = list(map(int,stdin.readline().split()))
a = [0]*(l+5)
b = [0] * (l+5)
x = list(map(int,stdin.readline().split()))
x.sort()
y = [0]*n
for i in range(2,l+1):
	if a[i]==0:
		cur = i
		while cur<=l:
			tm = cur
			co = 0
			while tm%i==0:
				tm/=i
				co+=1
			if co > b[cur]:
				b[cur] = co
				a[cur] = i
			cur+=i
			
lo = 0
hi = n-1
for st in range(1,l+1):
	ac = 0
	if st==1 or (a[st]%st)%2==1:
		ac = 1
	if ac==1:
		y[hi]+=1
	else:
		if y[lo]>0:
			y[lo]-=1
		else:
			x[lo]/=2
			if x[lo]==0:
				lo+=1
	if lo > hi:
		break
mo = 10**9 + 7
print(hi-lo+1)
for i in range(lo,hi+1):
	print((x[i]*pow(2,y[i],mo))%mo, end=' ')