Source Code
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll N = 1000000;
const ll M = N * N;

ll k;
int n;
vector<pll> a;

int main() {
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        ll x, y;
        scanf("%lld%lld", &x, &y);
        if (x <= N && x * x <= k) {
            a.emplace_back(y, x);
        }
    }
    sort(a.begin(), a.end());

    ll old = 0;
    ll answer = 0;
    vector<ll> subs;
    vector<ll> newsubs;
    for (pll p : a) {
        ll y = p.second;
        ll x = y * y;

        ll current = old;
        if (x <= k) {
            newsubs.push_back(x);
            current += k / x;
        }
        for (ll z : subs) {
            if (abs(z * y) <= k && abs(z * x) <= k) {
                newsubs.push_back(-z * x);
                current += k / (-z * x);
            }
        }

        subs = newsubs;

        ll now = current - old;
        answer += now * p.first;
        old = current;
    }

    cout << answer << endl;
}
Copy
Number of the Beast Baraa_Armoush
GNU G++17
1091 ms
3.0 MB
Time Limit Exceeded