1503 . 小苗排磁磚

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

alvingogo

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

33.3% (2/6)

Tags

ytp ytp2026 ytp-senior

Description

小苗最近迷上了用磁磚拼長方形。他把 $n$ 塊磁磚排成 $a$ 列 $b$ 行算一種排法，其中 $a \times b = n$。他覺得轉個方向擺在地板上就是不同的感覺，所以 $a$ 列 $b$ 行和 $b$ 列 $a$ 行算兩種不同的排法。

小苗一邊排磁磚，一邊記下每種數量有幾種排法。他發現有些數量特別討喜；比如 $4$ 塊磁磚恰好有 $3$ 種排法，$9$ 塊也恰好有 $3$ 種。$3$ 是奇質數，看起來不多不少，剛剛好。相比之下，$12$ 塊磁磚有 $6$ 種排法，反而讓他覺得有點雜亂。小苗把排法數量剛好是奇質數的正整數稱為整齊數。

後來小苗到一間磁磚店打工。店裡賣磁磚組合包，數量從 $L$ 塊到 $R$ 塊，每種數量都有恰好一種組合包。他想知道，其中有幾種組合包的數量是整齊數？

Input Format

第一行有兩個正整數 $L$、$R$，代表店裡組合包數量的最小值與最大值。

  • $1 \leq L \leq R \leq 10^ {12}$

Output Format

輸出一個整數，代表數量是整齊數的組合包種數。

Sample Input 1

1 10

Sample Output 1

2

Hints

範測 1 解釋：

$[1, 10]$ 中是整齊數的只有 $4$ 與 $9$，各恰有 $3$ 種排法。

以 $4$ 為例，有「$1$ 列 $4$ 行」、「$2$ 列 $2$ 行」、「$4$ 列 $1$ 行」這 $3$ 種排法。

Problem Source

2026 YTP 高中組決賽 p2

Subtasks

No. Testdata Range Constraints Score
1 0 範例測試資料 0
2 0~9 $R \leq 10^ 6$ 3
3 0~19 無額外限制 7

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 1048576 65536 1 2 3
1 1000 1048576 65536 2 3
2 1000 1048576 65536 2 3
3 1000 1048576 65536 2 3
4 1000 1048576 65536 2 3
5 1000 1048576 65536 2 3
6 1000 1048576 65536 2 3
7 1000 1048576 65536 2 3
8 1000 1048576 65536 2 3
9 1000 1048576 65536 2 3
10 1000 1048576 65536 3
11 1000 1048576 65536 3
12 1000 1048576 65536 3
13 1000 1048576 65536 3
14 1000 1048576 65536 3
15 1000 1048576 65536 3
16 1000 1048576 65536 3
17 1000 1048576 65536 3
18 1000 1048576 65536 3
19 1000 1048576 65536 3
Submit
Back to Top