y8ctgt - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 5e2 + 5;
int dp[maxn][maxn], f[maxn][maxn], g[maxn][maxn];
int p[8] = {2, 3, 5, 7, 11, 13, 17, 19};
array<int, 2> a[maxn];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, mod; cin >> n >> mod;
    for(int i = 1; i <= n - 1; i++){
        a[i][0] = -1;
        a[i][1] = 0;
        int cur = i + 1;
        for(int j = 0; j <= 7; j++){
            while(cur % p[j] == 0){
                cur /= p[j];
                a[i][1] |= (1 << j);
            }
        }
        if(cur != 1) a[i][0] = cur;
    }
    sort(a + 1, a + n);

    dp[0][0] = 1;
    for(int i = 1; i < n; i++){
        if(i == 1 || a[i][0] != a[i - 1][0] || a[i][0] == -1){
             for(int j = 0; j <= 255; j++) for(int k = 0; k <= 255; k++) f[j][k] = g[j][k] = dp[j][k];
        }
        for(int j = 255; j >= 0; j--){
            for(int k = 255; k >= 0; k--){
                if((j & k) == 0){
                    if((a[i][1] & j) == 0) (g[j][k | a[i][1]] += g[j][k]) %= mod;
                    if((a[i][1] & k) == 0) (f[j | a[i][1]][k] += f[j][k]) %= mod;
                }
            }
        }
        if(i == n - 1 || a[i][0] != a[i + 1][0] || a[i][0] == -1){
            for(int j = 0; j <= 255; j++){
                for(int k = 0; k <= 255; k++){
                    if((j & k) == 0) dp[j][k] = (f[j][k] + g[j][k] - dp[j][k] + mod) % mod;
                }
            }
        }
    }
    int ans = 0;
    for(int j = 0; j <= 255; j++){
        for(int k = 0; k <= 255; k++){
            if((j & k) == 0){
                (ans += dp[j][k]) %= mod;
            }
        }
    }
    cout << (ans + mod) % mod;
}