#P1902. Zju2116 Christopher

    ID: 925 传统题 1000ms 512MiB 尝试: 244 已通过: 92 难度: 5 上传者: 标签>CF1800普及+/提高-Lucas 定理补集计数乘法原理进位制转换高精度除法高精度乘法高精度减法

Zju2116 Christopher

题目描述

给定n个元素,要从中间选择m个元素有多少种方案呢?答案很简单,就是 (nm){n\choose m}。如果一个整数m(0≤m≤n)m(0\leq m\leq n),(nm){n\choose m}是某一个质数p的倍数,那么这个m就是讨厌的数字,现在给定了p和n,求有多少个讨厌的数字。

输入格式

第一行是一个正整数n(1≤n≤10100)n(1≤n≤10^{100})。输入的第二行是一个质数 p(1≤p≤107)p(1≤p≤10^7)。

输出格式

只有一行,表示讨厌的数字的个数。

6
2

3

提示

30%的数据里,n≤1000n≤1000;

100%的数据里,n≤10100n≤10^{100}

题目来源

没有写明来源