161 . 簡單數學

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

100.0% (9/9)

Tags

ioicamp ioicamp-2022

Description

小風是熱愛數學的小孩，今天剛聽完數學講師精彩的課程，他迫不及待想要練習數學習題，以下是他遇到的問題：

對於一個正整數 $n$，定義 $f(n)$ 為最大的正整數 $k$ 使得存在正整數 $d > 1$ 讓 $n$ 被 $d^ k$ 整除，給定正整數 $N, K$ 請計算對於每個整數 $k=1, 2, \ldots, K$，在 $[1, N]$ 中有多少數 $n$ 使得 $f(n) = k$？

Input Format

輸入只有一行，包含兩個正整數 $N, K$。

  • $1 \leq N \leq 10^ {12}$
  • $1 \leq K \leq 10^ 6$

Output Format

請輸出一行包含 $K$ 個數字，第 $k$ 個輸字代表有多少個 $[1, N]$ 中的正整數 $n$ 使得 $f(n) = k$。

Sample Input 1

5 2

Sample Output 1

3 1

Sample Input 2

10 3

Sample Output 2

6 2 1

Sample Input 3

1000000000000 5

Sample Output 3

607927102273 223980270248 92031030404 40448937502 18565251839

Hints

在 Sample Test 2 中，
$f(1) = 0, f(2) = 1, f(3) = 1, f(4) = 2, f(5) = 1,$
$ f(6) = 1, f(7) = 1, f(8) = 3, f(9) = 2, f(10) = 1$。

Problem Source

IOICamp 2022 Day2 pA

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~35 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 1 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 2
31 1000 262144 65536 2
32 1000 262144 65536 2
33 1000 262144 65536 2
34 1000 262144 65536 2
35 1000 262144 65536 2
Submit
Back to Top