#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
[[maybe_unused]] typedef long long ll;
[[maybe_unused]] const int N = (int)1e6 + 54;
[[maybe_unused]] const int mod = (int)1e9 + 7;
[[maybe_unused]] char space = ' ';
void Run(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifndef ONLINE_JUDGE
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
#endif
}
int n,k;
vector<int> isPrime(N,1);
vector<int> primes;
ll fastPow(ll x,ll y) {
if (y == 0) {
return 1;
}
return fastPow(x,y / 2) * fastPow(x,y / 2) * (y % 2 ? x : 1);
}
void sieve() {
isPrime[0] = isPrime[1] = 0;
for (ll i = 2; i * i <= N; i++) {
if (!isPrime[i]) {
continue;
}
for (ll j = i * i; j * j <= N; j += i) {
isPrime[j] = 0;
}
primes.push_back(int(i));
}
}
vector<int> freq(N);
vector<int> ans;
map<int,int> primeDiv;
vector<int> divs;
void div(map<int,int> ::iterator i = primeDiv.begin(),int res = 1,int h = 0) {
if (i == primeDiv.end()) {
divs.push_back(res);
return;
}
auto temp = i;
temp++;
for (int j = 0; j <= i -> second; j++) {
div(temp,res * fastPow(i -> first,j));
}
}
void add(int h) {
primeDiv.clear();
divs.clear();
int temp = h;
for (const auto &item: primes) {
while (temp % item == 0) {
primeDiv[item]++;
temp /= item;
}
}
if (temp != 1) {
primeDiv[temp]++;
}
div(primeDiv.begin(),1,h);
}
int main()
{
Run();
//pre
sieve();
//in
int t = 1;
// cin >> t;
while (t--) {
cin >> n >> k;
vector<int> h(n);
for (int i = 0; i < n; i++) {
cin >> h[i];
}
//ops
ans.resize(n);
int cnt = 0;
for (const auto &item: h) {
freq[item] += item > k;
}
for (int i = 0; i < n; i++) {
if (h[i] > k) {
cnt++;
add(h[i] - k);
for (const auto &item: divs) {
ans[i] += freq[item];
}
}
}
//out
for (int i = 0; i < n; i++) {
cout << ans[i] + cnt * (h[i] == k) - (k == 0) << space;
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
8192 KB |
Output is correct |
2 |
Correct |
6 ms |
8148 KB |
Output is correct |
3 |
Correct |
131 ms |
9200 KB |
Output is correct |
4 |
Correct |
378 ms |
11384 KB |
Output is correct |
5 |
Correct |
138 ms |
9060 KB |
Output is correct |
6 |
Correct |
411 ms |
11340 KB |
Output is correct |
7 |
Correct |
142 ms |
9068 KB |
Output is correct |
8 |
Correct |
140 ms |
9060 KB |
Output is correct |
9 |
Correct |
398 ms |
11272 KB |
Output is correct |
10 |
Correct |
393 ms |
11128 KB |
Output is correct |