题解
怎么NOI2015D1……全是一眼秒的sb题……然后我代码全都写跪一遍= = 要是NOI2015是IOI赛制我就可以AK啦（大雾）
代码能力直线下降，NOI2018滚粗预定了啊TAT
我是不是要去开码农题啊QAQ
我们发现大于\(\sqrt{N}\)的素数只会在每个数里出现至多1个，而小于\(\sqrt{N}\)的素数只有8个
分别是
2 3 5 7 11 13 17 19
我们对于素因子只有这8个的数先做一遍dp，状态压缩是\(3^8\)每一位分别是0 1 2，表示这个素因子不在任何集合，这个素因子在1集合和这个素因子在2集合
每次判断这个数的素因子如果跨了两个集合就不合法，如果和1集合有交不可以放到2集合，和2集合有交不可以放到1集合
对于包含剩下素数的数，设这个大于\(\sqrt{N}\)的素数为p，按照上述过程做dp，设f[S]为1集合里包含有p作为素因子的数，g[S]为2集合里包含有p作为素因子的数
最后ans[S] = f[S] + g[S] - dp[S]（dp[S]是只包含8个素因子的数的方案数）
复杂度\(O(3^8 N)\)
代码
#include <bits/stdc++.h>
//#define ivorysi
#define enter putchar('\n')
#define space putchar(' ')
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eps 1e-8
#define mo 974711
#define MAXN 100005
#define pii pair<int,int>
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
bool nonprime[505];
int prime[505],tot;
int dp[2][7006],N,MOD,S[505],rem[505],a[10],b[10],f[2][7006],g[2][7006],s[7006];
int encode(int *a) {
int res = 0;
for(int i = 1 ; i <= 8 ; ++i) {
res = res * 3 + a[i];
}
return res;
}
void decode(int Sta,int *a) {
for(int i = 8 ; i >= 1 ; --i) {
a[i] = Sta % 3;
Sta /= 3;
}
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
int inc(int a,int b) {
a = a + b;
if(a >= MOD) a -= MOD;
return a;
}
void update(int &x,int y) {
x = x + y;
if(x >= MOD) x -= MOD;
}
void Init() {
read(N);read(MOD);
for(int i = 2 ; i <= 500 ; ++i) {
if(!nonprime[i]) {
prime[++tot] = i;
for(int j = 2 ; j <= 500 / i ; ++j) nonprime[i * j] = 1;
}
}
}
void Solve() {
for(int i = 2 ; i <= N ; ++i) {
int x = i;
for(int j = 1 ; j <= 8 ; ++j) {
if(x % prime[j] == 0) {
S[i] |= (1 << j - 1);
while(x % prime[j] == 0) x /= prime[j];
}
}
if(x > 1) rem[i] = x;
}
int t = 1;
for(int j = 1 ; j <= 8 ; ++j) t = t * 3;
int cur = 0;
dp[0][0] = 1;
for(int i = 2 ; i <= N ; ++i) {
if(rem[i]) continue;
memset(dp[cur ^ 1],0,sizeof(dp[cur ^ 1]));
for(int j = 0 ; j < t ; ++j) {
if(!dp[cur][j]) continue;
decode(j,a);
int s1 = 0,s2 = 0;
for(int k = 1 ; k <= 8 ; ++k) {
if(a[k] == 1) s1 |= (1 << k - 1);
else if(a[k] == 2) s2 |= (1 << k - 1);
}
update(dp[cur ^ 1][j],dp[cur][j]);
if((s1 & S[i]) && (s2 & S[i])) continue;
if(!(s2 & S[i])) {
memcpy(b,a,sizeof(a));
for(int k = 1 ; k <= 8 ; ++k) {
if(b[k]) continue;
if(S[i] >> (k - 1) & 1) b[k] = 1;
}
update(dp[cur ^ 1][encode(b)],dp[cur][j]);
}
if(!(s1 & S[i])) {
memcpy(b,a,sizeof(a));
for(int k = 1 ; k <= 8 ; ++k) {
if(b[k]) continue;
if(S[i] >> (k - 1) & 1) b[k] = 2;
}
update(dp[cur ^ 1][encode(b)],dp[cur][j]);
}
}
cur ^= 1;
}
int ans = 0;
for(int i = 9 ; i <= tot ; ++i) {
if(N < prime[i]) break;
int c = 0;
memcpy(f[c],dp[cur],sizeof(dp[cur]));
memcpy(g[c],dp[cur],sizeof(dp[cur]));
for(int j = 1 ; j <= N / prime[i] ; ++j) {
memset(f[c ^ 1],0,sizeof(f[c ^ 1]));
memset(g[c ^ 1],0,sizeof(g[c ^ 1]));
for(int k = 0 ; k < t ; ++k) {
decode(k,a);
update(f[c ^ 1][k],f[c][k]);
update(g[c ^ 1][k],g[c][k]);
int s1 = 0,s2 = 0;
for(int h = 1 ; h <= 8 ; ++h) {
if(a[h] == 1) s1 |= (1 << h - 1);
else if(a[h] == 2) s2 |= (1 << h - 1);
}
if((S[j] & s1) && (S[j] & s2)) continue;
if(!(S[j] & s2)) {
memcpy(b,a,sizeof(b));
for(int h = 1 ; h <= 8 ; ++h) {
if(b[h]) continue;
if(S[j] >> (h - 1) & 1) b[h] = 1;
}
update(f[c ^ 1][encode(b)],f[c][k]);
}
if(!(S[j] & s1)) {
memcpy(b,a,sizeof(b));
for(int h = 1 ; h <= 8 ; ++h) {
if(b[h]) continue;
if(S[j] >> (h - 1) & 1) b[h] = 2;
}
update(g[c ^ 1][encode(b)],g[c][k]);
}
}
c ^= 1;
}
for(int k = 0 ; k < t ; ++k) dp[cur][k] = inc(inc(f[c][k],g[c][k]),MOD - dp[cur][k]);
}
for(int k = 0 ; k < t ; ++k) update(ans,dp[cur][k]);
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve();
return 0;
}