Just Update and Print the array
All submissions for this problem are available.
You are given a 1-indexed array of size N. Initially, all elements of the array are zeros. You need to perform U updates to the array.
Each Update asks you to add 1 to the elements of the array at the indices specified by 'ax+b' for all non-negative integers x, where a and b are positive integers which specify an update query.
After performing all the updates to the array, print the array with every entry separated by space.
First Line of the input contains 2 space separated integers N, U.
Each of the next U lines contains 2 space-separated integers: a and b, specifying an update.
Output the array in a single line after all updates.
- 1 ≤ N ≤ 105
- 1 ≤ a, b ≤ N
- 1 ≤ U ≤ 2*105
Input: 7 4 1 3 7 7 7 3 2 2 Output: 0 1 2 2 1 2 2
ExplanationArray after first update : [0,0,1,1,1,1,1]
Array after second update : [0,0,1,1,1,1,2]
Array after third update : [0,0,2,1,1,1,2]
Array after fourth update : [0,1,2,2,1,2,2]
|Tags||acmkol15, devuy11, medium, offline, range-sum, sqrt-decomp|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.