摘要：from collections import defaultdictdef precompute_min_prime(max_num): min_prime = [0] * (max_num + 1) for i in range(2, max_num +
from collections import defaultdictdef precompute_min_prime(max_num): min_prime = [0] * (max_num + 1) for i in range(2, max_num + 1): if min_prime[i] == 0: min_prime[i] = i for j in range(i * i, max_num + 1, i): if min_prime[j] == 0: min_prime[j] = i return min_primedef get_square_free(x, min_prime): if x == 1: return 1 res = 1 while x > 1: p = min_prime[x] cnt = 0 while x % p == 0: x //= p cnt += 1 if cnt % 2 == 1: res *= p return resdef solve: n = int(input) arr = list(map(int, input.split)) max_num = max(arr) min_prime = precompute_min_prime(max_num) freq = defaultdict(int) for num in arr: sf = get_square_free(num, min_prime) freq[sf] += 1 max_freq = max(freq.values) print(n - max_freq)if __name__ == "__main__": solve 来源：君浩教育
免责声明：本站系转载，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本站联系，我们将在第一时间删除内容!
