161 . 簡單數學

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

90.0% (9/10)

Tags

ioicamp ioicamp-2022

Description

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

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

Input Format

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

  • 1≤N≤1012
  • 1≤K≤106

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