IOIC 2025 題目已公開！ 連結
程式解題社網站 程式解題社網站上線了！
NTUCPC OJ 現在支援 Rust ！
NTUCPCPC 2026 初賽 & 決賽題目已公開！ 連結
YTP 2026 題目已公開！ 連結
程式解題社網站 程式解題社網站上線了！
NTUCPC OJ 現在支援 Rust ！
NTUCPCPC 2026 初賽 & 決賽題目已公開！ 連結
YTP 2026 題目已公開！ 連結
1511 . 神奇的抽獎
TopCoder
Tags
Description
夜市裡面有一攤在辦抽獎。獎券從 $1$ 號印到 $N$ 號。老闆不比券號大小，而是把券號中的每個數字全部乘起來。例如，$1126$ 號就是 $1 \times 1 \times 2 \times 6 = 12$，$105$ 號就是 $1 \times 0 \times 5 = 0$。只要乘積能被今晚的幸運數字 $M$ 整除（$0$ 被任何數字整除），就能把大獎拿走。
小魚在攤子前站了很久，大獎是其次，他更想知道那疊獎券裡，到底有幾張會中獎。
老闆這攤會擺 $T$ 個晚上。每天都會重新印一疊從 $1$ 號到 $N$ 號的獎券，幸運數字 $M$ 也會跟著改變。
Input Format
第一行有一個整數 $T$，代表老闆總共擺幾個晚上。
接下來有 $T$ 行，每行有兩個整數 $N$ 和 $M$，$N$ 是這一晚獎券的最大號碼，$M$ 是這一晚的幸運數字。
- $1 \le T \le 100$
- $1 \le N \le 10^ {18}$
- $1 \le M \le 10^ {18}$
Output Format
對每一晚輸出一行，一個整數，代表這一晚會中獎的獎券有幾張。
Sample Input 1
3 100 10 20 3 9 1
Sample Output 1
18 8 9
Hints
範測 1 解釋：
第一晚 $N = 100$、$M = 10$：例如 $25$ 號的乘積為 $2 \times 5 = 10$、$30$ 號的乘積為 $3 \times 0 = 0$，都能被 $10$ 整除。$1$ 到 $100$ 中這樣的獎券共有 $18$ 張。
第二晚 $N = 20$、$M = 3$：共有 $8$ 張獎券的數字乘積能被 $3$ 整除。
第三晚 $N = 9$、$M = 1$：任何整數都能被 $1$ 整除，所以 $1$ 到 $9$ 全部中獎，共 $9$ 張。
Problem Source
2026 YTP 高中組決賽 p10
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測試資料 | 0 |
| 2 | 1~7 | $N \le 10^ 5$ | 2 |
| 3 | 8~14 | $M \le 10^ 4$ | 6 |
| 4 | 1~22 | 無額外限制 | 12 |