思路与算法

将2到n的每个数分解。因为23²>500，大于19的质因子至多有一个；其余质因子由2、3、5、7、11、13、17、19这8个素数的掩码表示。设dp[A,B]为两人的小素数集合恰为A、B时的方案数，只保存A∩B为空的状态。相同大质因子的数分为一组；没有大质因子的数各自单独成组。对一组从旧dp各复制出G、W两张表，G仅允许本组数给第一人或不选，W仅允许给第二人或不选。组内每个数用掩码并集转移，若与对方掩码相交则不可选。状态按编码递减遍历保证每个数至多使用一次；并集不变的状态恰好翻倍。组末令新dp=G+W-旧dp，因为全组不选被重复计数一次。最后求所有合法状态之和并对p取模。

正确性说明

不和谐当且仅当两人的已选数共享某个质因子。掩码互斥精确排除8个小素数冲突；相同大质因子的一组只向一个人开放，精确排除所有大素数冲突。不同大素数组之间不存在遗漏的大质因子冲突。组内每种物品有不选和给指定人的两种决定，递减的0/1转移恰好计数每个子集。两张表的交集正是全组不选，因此扣除旧dp后所有合法本组决定恰计一次。按组归纳，最终状态穷尽且不重不漏。两人均可空集，初态dp[0,0]=1。

复杂度

令g为分组数，K=8。分解和分组耗时O(nK log n+n log n)；合法掩码对有3^K个，每个数做两次转移O(n3^K)，每组复制及合并完整数组O(g4^K)。初始化数组O(4^K)，总空间O(4^K+n)。代码中每个表有65536项，合法状态6561个。

易错点

大质因子不是按“是否存在”合为一组，而是按其具体值分组；没有大质因子的数分别成组。必须扣除全组不选的重复。正文规定p为正整数，数据表的0下界与正文相交后仍为p>=1；p=1时初态及全部结果均为0。加减模用足够宽的临时整数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, p;
    cin >> n >> p;
    vector<int> pr = {2, 3, 5, 7, 11, 13, 17, 19};
    map<int, vector<int>> groups;
    for (int x = 2; x <= n; x++) {
        int v = x, mask = 0;
        for (int j = 0; j < 8; j++)
            if (v % pr[j] == 0) {
                mask |= 1 << j;
                while (v % pr[j] == 0)
                    v /= pr[j];
            }
        groups[v == 1 ? -x : v].push_back(mask);
    }
    vector<int> states;
    for (int a = 0; a < 256; a++)
        for (int b = 0; b < 256; b++)
            if (!(a & b))
                states.push_back((a << 8) | b);
    vector<int> dp(65536), a, b;
    dp[0] = 1 % p;
    for (auto &g : groups) {
        a = b = dp;
        for (int m : g.second)
            for (int z = (int)states.size() - 1; z >= 0; z--) {
                int s = states[z], x = s >> 8, y = s & 255;
                if (!(m & y)) {
                    int t = ((x | m) << 8) | y;
                    a[t] = (a[t] + a[s]) % p;
                }
                if (!(m & x)) {
                    int t = (x << 8) | (y | m);
                    b[t] = (b[t] + b[s]) % p;
                }
            }
        for (int s : states)
            dp[s] = ((long long)a[s] + b[s] - dp[s] + p) % p;
    }
    long long ans = 0;
    for (int s : states)
        ans = (ans + dp[s]) % p;
    cout << ans << '\n';
}