{"problem":{"name":"P-smooth number","description":{"content":"A positive integer is called a $k$\\-smooth number if none of its prime factors exceeds $k$.   Given an integer $N$ and a prime $P$ not exceeding $100$, find the number of $P$\\-smooth numbers not excee","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc300_g"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $N$ is an integer such that $1 \\le N \\le 10^{16}$.\n*   $P$ is a prime such that $2 \\le P \\le 100$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $P$\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"一个正整数称为 $k$-平滑数，如果它的所有质因数都不超过 $k$。给定一个整数 $N$ 和一个不超过 $100$ 的质数 $P$，找出不超过 $N$ 的 $P$-平滑数的个数。\n\n## Constraints\n\n*   $N$ 是一个整数，满足 $1 \\le N \\le 10^{16}$。\n*   $P$ 是一个质数，满足 $2 \\le P \\le 100$。\n\n## Input\n\n输入从标准输入给出，格式如下：\n\n$N$ $P$\n\n[samples]","is_translate":true,"language":"Chinese"}],"meta":{"iden":"abc300_g","tags":[],"sample_group":[["36 3","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$."],["10000000000000000 97","2345134674"]],"created_at":"2026-03-03 11:01:14"}}