Zju2116 Christopher’s Christmas Letter

Time Limit:1000MS  Memory Limit:65536K
Total Submit:4 Accepted:3

Description

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

Input

第一行是一个正整数n，(1≤n≤10100)。
输入的第二行是一个质数p(1≤p≤107)。

Output

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

Sample Input

6
2

Sample Output

3

Hint

30%的数据里，n≤1000;
100%的数据里，n≤10^100

Source

By Zzy
数学题。。我证了半天证明了设n的p进制表示为a0a1a2a3不讨厌的数字个数就是
(a0+1)*(a1+1)*(a2+1)。。。然后减一下就可以了。。
证明过程主要是因为打不出公式很难发出来。。主要是利用多项式的拆分。。