array filling problem code arrfill

Solutions on MaxInterview for array filling problem code arrfill by the best coders in the world

showing results for - "array filling problem code arrfill"
Greta
10 Jun 2017
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4
5int main()
6{
7  ios_base::sync_with_stdio(0);
8  cin.tie(0);
9  cout.tie(0);
10  
11  int t;
12  cin >> t;
13  while(t--) {
14    ll n, m;
15    cin>>n>>m;
16
17    vector<pair<int,int>>vp;
18    for (int i=0; i < m; i++)
19    {
20      ll x, y;
21      cin>>x>>y;
22      vp.push_back({x,y});
23    }
24
25    sort(vp.begin(), vp.end(), greater<pair<int,int>>());
26    
27    ll lcm=1;
28    ll rem=n;
29    ll res=0;
30    
31
32    for (int i=0; i<m && rem>0; i++){
33        ll a= vp[i].first,b=vp[i].second;
34        lcm = lcm*b/__gcd(lcm,b);
35        res += (rem-n/lcm)*a;
36        rem= n/lcm;
37    }
38
39    cout <<res<<endl;
40  }
41  return 0;
42}