记录编号	597569	评测结果	AAAAAAAAAA
题目名称	仪式感	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	3.860 s
提交时间	2024-11-29 22:18:10	内存使用	33.97 MiB

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second

using i64 = long long;
using pii = std::pair<int, int>;

constexpr int maxn = 3e5 + 5, mod = 998244353;
int n, m, a[maxn], w, cnt[maxn], mnx[maxn], buc[maxn], tmp[maxn], mu[maxn];
bool flg[maxn];
std::vector<int> G[maxn];

void add(int& x, int y) { if ((x += y) >= mod) x -= mod; return; }
int dec(int x, int y) { return (x - y) < 0 ? (x - y + mod) : (x - y); }

int gcd(int x, int y) {
	return y ? gcd(y, x % y) : x;
}

int power(int x, int y) {
	int ans = 1;
	for (; y; y >>= 1) {
		if (y & 1) ans = 1ll * ans * x % mod;
		x = 1ll * x * x % mod;
	}
	return ans;
}

namespace binom {
	std::vector<int> fac, ifac, inv;
	void init(int n) {
		fac.resize(n + 5, 0);
		ifac.resize(n + 5, 0);
		inv.resize(n + 5, 0);
		fac[0] = 1;
		for (int i = 1; i <= n; ++i) {
			fac[i] = 1ll * fac[i - 1] * i % mod;
		}
		ifac[n] = power(fac[n], mod - 2);
		for (int i = n - 1; i >= 0; --i) {
			ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
		}
		return;
	}
	int C(int n, int m) {
		if (n < 0 || m < 0 || n < m) return 0;
		return 1ll * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
	}
}

using namespace binom;

int main() {
	freopen("yishigan.in", "r", stdin);
	freopen("yishigan.out", "w", stdout);
	std::cin.tie(nullptr)->sync_with_stdio(false);
	std::cin >> n >> m; init(n);
	for (int i = 1; i <= n; ++i) {
		std::cin >> a[i];
		w = std::max(w, a[i]);
		++buc[a[i]], ++cnt[a[i]];
	}
	for (int i = 1; i <= w; ++i) {
		for (int j = i; j <= w; j += i) {
			G[j].pb(i);
		}
	}
	std::vector<int> pri;
	mu[1] = 1;
	for (int i = 2; i <= w; ++i) {
		if (!flg[i]) {
			pri.pb(i);
			mu[i] = mod - 1;
		}
		for (int j = 0; j < (int)pri.size() && i * pri[j] <= w; ++j) {
			flg[i * pri[j]] = true;
			if (i % pri[j]) {
				mu[i * pri[j]] = mod - mu[i];
			} else {
				break;
			}
		}
	}
	for (auto& p : pri) {
		for (int i = w / p; i >= 1; --i) {
			cnt[i] += cnt[i * p];
		}
	}
	std::fill(mnx + 1, mnx + 1 + w, (int)1e9);
	for (int k = 1; k <= 20; ++k) {
		for (int i = 1; i <= m; ++i) {
			int c = 0;
			for (int j = 1; i * j <= w; ++j) {
				if (!mu[j] || cnt[i * j] < k) continue;
				add(c, 1ll * C(cnt[i * j], k) * mu[j] % mod);
			}
			if (c) {
				mnx[i] = std::min(mnx[i], k);
			}
		}
	}
	for (int i = 1; i <= m; ++i) {
		if (mnx[i] <= 20) {
			std::cout << mnx[i] << ' ' << cnt[i] << '\n';
		} else {
			std::cout << "-1 -1\n";
		}
	}
	return 0;
}