#include #include #include #include typedef struct union_find { int32_t *parent; int32_t size; } union_find; void init_union_find (union_find * const u) { for (int32_t i = 0; i < u->size; ++i){ u->parent[i] = -1; } } union_find* new_union_find (const int32_t size) { union_find *u = (union_find *) calloc (1, sizeof (union_find)); u->parent = (int32_t *) calloc (size, sizeof (int32_t)); u->size = size; init_union_find (u); return u; } void free_union_find (union_find * const u) { free (u->parent); free (u); } int32_t root (union_find * const u, int32_t x) { int32_t index[32]; int32_t top = 0; while (u->parent[x] >= 0) { index[top++] = x; x = u->parent[x]; } while (top > 0) { u->parent[index[--top]] = x; } return x; } int same (union_find * const u, const int32_t x, const int32_t y) { return root (u, x) == root (u, y); } int32_t get_size (union_find * const u, const int32_t x) { return - (u->parent[root (u, x)]); } void unite (union_find * const u, int32_t x, int32_t y) { x = root (u, x); y = root (u, y); if (x == y) return; if (u->parent[x] > u->parent[y]) { const int32_t swap = x; x = y; y = swap; } u->parent[x] += u->parent[y]; u->parent[y] = x; } typedef int32_t i32; void run (void) { i32 n, p; scanf ("%" SCNi32 "%" SCNi32, &n, &p); union_find *u = new_union_find (n + 1); for (i32 i = 2; 2 * i <= n; ++i) { for (i32 j = 2 * i; j <= n; j += i) { unite (u, j, j - i); } } printf ("%" PRIi32 "\n", get_size (u, p)); } int main (void) { run(); return 0; }