P-smooth number

AtCoder

IDabc300_g

Time4000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

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 exceeding $N$. ## Constraints * $N$ is an integer such that $1 \le N \le 10^{16}$. * $P$ is a prime such that $2 \le P \le 100$. ## Input The input is given from Standard Input in the following format: $N$ $P$ [samples]

一个正整数称为 $k$-平滑数，如果它的所有质因数都不超过 $k$。给定一个整数 $N$ 和一个不超过 $100$ 的质数 $P$，找出不超过 $N$ 的 $P$-平滑数的个数。 ## Constraints * $N$ 是一个整数，满足 $1 \le N \le 10^{16}$。 * $P$ 是一个质数，满足 $2 \le P \le 100$。 ## Input 输入从标准输入给出，格式如下： $N$ $P$ [samples]

Samples

Input #1

36 3

Output #1

14

The $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$.  
Note that $1$ is a $k$\-smooth number for all primes $k$.

Input #2

10000000000000000 97

Output #2

2345134674

API Response (JSON)

{
  "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 excee...",
      "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输入从标准输...",
      "is_translate": true,
      "language": "Chinese"
    }
  ]
}

Full JSON Raw Segments