C++11(clang++ 3.9) 解法, 执行用时: 77ms, 内存消耗: 384K, 提交时间: 2019-11-09 14:04:01

#include <bits/stdc++.h>//§//
using namespace std;
int p[] = {2, 3, 5, 7, 11, 13, 17, 19}, mod;
int b[520], v[520], w[520], c1[520], c2[520], n, ans;
int main() {
	scanf("%d%d", &n, &mod);
	b[0] = 1;
	for (int i = 1; i <= 500; i++) {
		b[i] = b[i - 1] * 2 % mod;
	}
	for (int i = 1; i <= n; i++) {
		v[i] = i;
		for (int j = 0; j < 8; j++) {
			while (v[i] % p[j] == 0) {
				v[i] /= p[j];
				w[i] |= 1 << j;
			}
		}
	}
	for (int i = 0; i < 1 << 8; i++) {
		for (int j = 0; j < 1 << 8; j++) {
			if (i & j) {
				continue;
			}
			int t = __builtin_popcount(i | j) & 1;
			memset(c1, 0, sizeof c1);
			memset(c2, 0, sizeof c2);
			for (int k = 2; k <= n; k++) {
				if ((i & w[k]) == w[k]) {
					c1[v[k]]++;
				}
				if ((j & w[k]) == w[k]) {
					c2[v[k]]++;
				}
			}
			long long tmp = b[c1[1] + c2[1]];
			for (int k = 2; k <= n; k++) {
				tmp = tmp * (b[c1[k]] + b[c2[k]] - 1) % mod;
			}
			if (t) {
				ans += mod - tmp;
			} else {
				ans += tmp;
			}
			ans %= mod;
		}
	}
	printf("%d\n", ans);
	return 0;
}