Source Code
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[]{ -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[]{ 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
	return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
	return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
#else
#endif
}

const int N = 1e6;
int lpf[N + 1], cost[N + 1];
ll ans[N + 1];
void sieve() {
	for (int i = 0; i <= N; i++)
		lpf[i] = ((i & 1) ? i : 2);
	for (int i = 3; i * i <= N; i += 2)
		if (lpf[i] == i)
			for (int j = i * i; j <= N; j += i + i)
				if (lpf[j] == j)
					lpf[j] = i;
}

int main() {
	run();
	sieve();
	memset(cost, INF, sizeof cost);
	int n;
	ll k;
	cin >> n >> k;
	vector<pair<ll, int>> v;
	for (int i = 0; i < n; i++) {
		ll p;
		int c;
		cin >> p >> c;
		if (p <= N)
			cost[p] = c;
	}
	for (int x = 2; 1LL * x * x <= k; x++) {//x^2*y<=k
		vector<int> p;
		int tmp = x;
		while (tmp > 1) {
			p.push_back(lpf[tmp]);
			tmp /= lpf[tmp];
		}
		int mn = INF;
		for (auto& it : p)
			mn = min(mn, cost[it]);
		if (mn == (int)INF)
			continue;
		ans[x] = 1LL * mn * ((k / x) / x);
	}
	ll sum = 0;
	int x = 2;
	while (1LL * x * x <= k)
		x++;
	for (x--; x >= 2; x--) {
		for (int j = x + x; j <= N; j += x)
			ans[x] -= ans[j];
		sum += ans[x];
	}
	cout << sum << endl;
}
Copy
Number of the Beast AhmedEzzatG
GNU G++17
8 ms
8.4 MB
Wrong Answer