#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;
unordered_map<int, int> factorize(int n) {
unordered_map<int, int> factors;
while (n % 2 == 0) {
factors[2]++;
n /= 2;
}
for (int i = 3; i <= sqrt(n); i += 2) {
while (n % i == 0) {
factors[i]++;
n /= i;
}
}
if (n > 2) {
factors[n]++;
}
return factors;
}
int max_divisible_elements(vector<int>& arr, int k) {
unordered_map<int, int> prime_factors_count;
for (int num : arr) {
unordered_map<int, int> factors = factorize(num);
for (auto& factor : factors) {
prime_factors_count[factor.first] += factor.second;
}
}
int max_divisible = 0;
for (auto& factor : prime_factors_count) {
max_divisible = max(max_divisible, factor.second / k);
}
return max_divisible;
}
int main() {
vector<int> arr = {1, 2, 3, 4, 5, 6};
int k = 6;
cout << max_divisible_elements(arr, k) << endl; // Output: 2
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPGNtYXRoPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnVub3JkZXJlZF9tYXA8aW50LCBpbnQ+IGZhY3Rvcml6ZShpbnQgbikgewogICAgdW5vcmRlcmVkX21hcDxpbnQsIGludD4gZmFjdG9yczsKICAgIHdoaWxlIChuICUgMiA9PSAwKSB7CiAgICAgICAgZmFjdG9yc1syXSsrOwogICAgICAgIG4gLz0gMjsKICAgIH0KICAgIGZvciAoaW50IGkgPSAzOyBpIDw9IHNxcnQobik7IGkgKz0gMikgewogICAgICAgIHdoaWxlIChuICUgaSA9PSAwKSB7CiAgICAgICAgICAgIGZhY3RvcnNbaV0rKzsKICAgICAgICAgICAgbiAvPSBpOwogICAgICAgIH0KICAgIH0KICAgIGlmIChuID4gMikgewogICAgICAgIGZhY3RvcnNbbl0rKzsKICAgIH0KICAgIHJldHVybiBmYWN0b3JzOwp9CgppbnQgbWF4X2RpdmlzaWJsZV9lbGVtZW50cyh2ZWN0b3I8aW50PiYgYXJyLCBpbnQgaykgewogICAgdW5vcmRlcmVkX21hcDxpbnQsIGludD4gcHJpbWVfZmFjdG9yc19jb3VudDsKICAgIGZvciAoaW50IG51bSA6IGFycikgewogICAgICAgIHVub3JkZXJlZF9tYXA8aW50LCBpbnQ+IGZhY3RvcnMgPSBmYWN0b3JpemUobnVtKTsKICAgICAgICBmb3IgKGF1dG8mIGZhY3RvciA6IGZhY3RvcnMpIHsKICAgICAgICAgICAgcHJpbWVfZmFjdG9yc19jb3VudFtmYWN0b3IuZmlyc3RdICs9IGZhY3Rvci5zZWNvbmQ7CiAgICAgICAgfQogICAgfQogICAgCiAgICBpbnQgbWF4X2RpdmlzaWJsZSA9IDA7CiAgICBmb3IgKGF1dG8mIGZhY3RvciA6IHByaW1lX2ZhY3RvcnNfY291bnQpIHsKICAgICAgICBtYXhfZGl2aXNpYmxlID0gbWF4KG1heF9kaXZpc2libGUsIGZhY3Rvci5zZWNvbmQgLyBrKTsKICAgIH0KICAgIAogICAgcmV0dXJuIG1heF9kaXZpc2libGU7Cn0KCmludCBtYWluKCkgewogICAgdmVjdG9yPGludD4gYXJyID0gezEsIDIsIDMsIDQsIDUsIDZ9OwogICAgaW50IGsgPSA2OwogICAgY291dCA8PCBtYXhfZGl2aXNpYmxlX2VsZW1lbnRzKGFyciwgaykgPDwgZW5kbDsgLy8gT3V0cHV0OiAyCiAgICByZXR1cm4gMDsKfQ==