Trại Hè Hùng Vương - Tin 10 - Bài 1

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define FILENAME "DATA"
using namespace std;

const ll mod = 1e9+7;
const ll oo = 1e18;
const int maxn = 1e5;

int n,k;
int a[maxn+1];
ll s[maxn+1];
ll res = oo;

vector<int> p;
vector<bool> prime(maxn * 20 + 1, true);



void sang(){
	prime[0] = prime[1] = false;
	for (int i=2;i * i <= maxn;i++) {
		if (!prime[i]) continue;
		for (int j = i * i;j <= maxn;j+=i) prime[j] = false;
	}
	for (int i=2;i <= maxn;i++) if (prime[i]) p.pb(i);
}

ll get(ll x) {
	if (x <= 2) return abs(2 - x);
	int l=0,r=p.size()-1;
	int mid;
	int vt = 0;
	while(l <= r) {
		mid = l + (r-l) / 2;
		if (p[mid] < x) l = mid + 1;
		else {
			vt = mid;
			r = mid - 1;
		}
	}
	ll diff = abs(x - p[vt]);
	diff = min(diff, x - p[vt-1]);
	return diff;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	sang();
	cin >> n >> k;
	for (int i=1;i <= n;i++) cin >> a[i];
	s[0] = 0;
	for (int i=1;i <= n;i++) {
		s[i] = s[i-1];
		s[i] += get(a[i]);
	}

	for (int i=k;i <= n;i++) {
		res = min(res, s[i] - s[i-k]);
	}
	cout << res;

	return 0;
}

//hieuhfgr