1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
struct Num{
int a, b;
}s[505];
int n, p, f[265][265], g[2][265][265];
const int pri[]={2, 3, 5, 7, 11, 13, 17, 19};
bool cmp(Num u, Num v){
return u.b<v.b;
}
int main(){
cin>>n>>p;
for(int i=2; i<=n; i++){
int x=i;
for(int j=0; j<8; j++)
if(x%pri[j]==0){
s[i].a |= 1<<j;
while(x%pri[j]==0) x /= pri[j];
}
s[i].b = x;
}
sort(s+2, s+1+n, cmp);
f[0][0] = 1;
for(int i=2; i<=n; i++){
if(i==2 || s[i].b==1 || s[i].b!=s[i-1].b){
memcpy(g[0], f, sizeof(f));
memcpy(g[1], f, sizeof(f));
}
for(int j=(1<<8)-1; j>=0; j--)
for(int k=(1<<8)-1; k>=0; k--){
if(j&k) continue;
g[0][j|s[i].a][k] = (g[0][j|s[i].a][k] + g[0][j][k]) % p;
g[1][j][k|s[i].a] = (g[1][j][k|s[i].a] + g[1][j][k]) % p;
}
if(i==n || s[i].b==1 || s[i].b!=s[i+1].b)
for(int j=(1<<8)-1; j>=0; j--)
for(int k=(1<<8)-1; k>=0; k--){
if(j&k) continue;
f[j][k] = ((g[0][j][k] + g[1][j][k]) % p - f[j][k] + p) % p;
}
}
int ans=0;
for(int j=(1<<8)-1; j>=0; j--)
for(int k=(1<<8)-1; k>=0; k--){
if(j&k) continue;
ans = (ans + f[j][k]) % p;
}
cout<<ans<<endl;
return 0;
}
|