{"raw_statement":[{"iden":"problem statement","content":"A positive integer is called a $k$\\-smooth number if none of its prime factors exceeds $k$.  \nGiven an integer $N$ and a prime $P$ not exceeding $100$, find the number of $P$\\-smooth numbers not exceeding $N$."},{"iden":"constraints","content":"*   $N$ is an integer such that $1 \\le N \\le 10^{16}$.\n*   $P$ is a prime such that $2 \\le P \\le 100$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $P$"},{"iden":"sample input 1","content":"36 3"},{"iden":"sample output 1","content":"14\n\nThe $3$\\-smooth numbers not exceeding $36$ are the following $14$ integers: $1,2,3,4,6,8,9,12,16,18,24,27,32,36$.  \nNote that $1$ is a $k$\\-smooth number for all primes $k$."},{"iden":"sample input 2","content":"10000000000000000 97"},{"iden":"sample output 2","content":"2345134674"}],"translated_statement":[{"iden":"problem statement","content":"一个正整数称为 $k$-平滑数，如果它的所有质因数都不超过 $k$。给定一个整数 $N$ 和一个不超过 $100$ 的质数 $P$，找出不超过 $N$ 的 $P$-平滑数的个数。"},{"iden":"constraints","content":"*   $N$ 是一个整数，满足 $1 \\le N \\le 10^{16}$。\n*   $P$ 是一个质数，满足 $2 \\le P \\le 100$。"},{"iden":"input","content":"输入从标准输入给出，格式如下：\n\n$N$ $P$"},{"iden":"sample input 1","content":"36 3"},{"iden":"sample output 1","content":"14\n\n不超过 $36$ 的 $3$-平滑数是以下 $14$ 个整数：$1,2,3,4,6,8,9,12,16,18,24,27,32,36$。\n注意，$1$ 是所有质数 $k$ 的 $k$-平滑数。"},{"iden":"sample input 2","content":"10000000000000000 97"},{"iden":"sample output 2","content":"2345134674"}],"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}