e209. C(n, k) Again! - 高中生程式解題系統

內容

令 $n, k (k \leq n)$ 為非負整數，定義 $C_{k}^{n} = \frac{n!}{k! (n - k)!}$ ，很顯然地，我們可以從組合意義上得知 $C_{k}^{n}$ 也是整數。

想要證明 $\frac{n!}{k! (n - k)!}$ 是整數，不妨提出 $(n - k)!$ ，改為證明任意連續 $k$ 個非負整數的乘積皆能被 $k!$ 整除。

現在有兩個大小為 $k$ 的集合 $S = {x | x \in N, 1 \leq x \leq k}, T = {y | y \in N, m \leq y \leq m + k - 1}$ 。

請在 $S, T$ 間建立若干條「邊」，滿足下列性質：

1. 權重大於 1。

2. 對於所有 $x \in S$ ，其連接的邊權重乘積(沒有邊視為 1)恰為 $x$ 。

3. 對於所有 $y \in T$ ，其連接的邊權重乘積(沒有邊視為 1)為 $y$ 的因數。

輸入說明

兩個正整數 $m, k (m \leq 10^{9}, k \leq 10^{6})$ 。

輸出說明

輸出共有 $k$ 行。

第 $x$ 行首先輸出一個非負整數 $d$ ，代表 $x (x \in S)$ 連接 $d$ 條邊，接著輸出 $d$ 個數對 $y w$ ，表示 $x$ 和 $y \in T$ 有一條權重為 $w$ 的邊。數字以空格隔開，行尾不應有多餘空白。

範例輸入 #1

範例輸入 1:
5 4

範例輸入 2:
5 4

範例輸入 3:
1 4

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 0.5s , <1K
公開測資點#1 (5%): 0.5s , <1K
公開測資點#2 (5%): 0.5s , <1K
公開測資點#3 (5%): 0.5s , <1K
公開測資點#4 (5%): 0.5s , <1K
公開測資點#5 (5%): 0.5s , <1K
公開測資點#6 (5%): 0.5s , <1K
公開測資點#7 (5%): 0.5s , <1K
公開測資點#8 (5%): 0.5s , <1K
公開測資點#9 (5%): 0.5s , <1K
公開測資點#10 (5%): 0.5s , <1K
公開測資點#11 (5%): 0.5s , <1K
公開測資點#12 (5%): 0.5s , <1K
公開測資點#13 (5%): 3.0s , <1K
公開測資點#14 (5%): 3.0s , <1K
公開測資點#15 (5%): 3.0s , <1K
公開測資點#16 (5%): 3.0s , <1K
公開測資點#17 (5%): 3.0s , <1K
公開測資點#18 (5%): 3.0s , <1K
公開測資點#19 (5%): 3.0s , <1K

提示：

如果你採用的解法會輸出極大量的數字，可以試著用 printf 代替 cout，或是進一步地優化輸出。

測資點 #00 ~ #06： $k \leq 5$ 。

測資點 #07 ~ #12： $k \leq 1000$ 。

測資點 #13 ~ #19： $k \leq 1000000$ 。

標籤:

出處:

[管理者： icube (!@#$%^&*()_...) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」