主唱太拼命了
祺祺在上幼稚園的時候在學排列組合,他的老師說:
對於兩個數字 n、k,若 0≤k≤n,則 (nk)=n!k!(n−k)! 代表「有 n 個相異的東西,從中選取 k 個的方法數」。老師也說這些 (nk) 會一下子就跑到很大!舉例來說,(202)=190,但是 (2010) 就會飛到 184756 了!
陷入了沈思的祺祺馬上就想到了一個問題:有幾個 n,k 滿足 0≤k≤n,且 (nk) 在 l 與 r 之間呢?因為他發現對於任何的 x,皆有 (x0)=1,所以他還多加了一個限制 N,表示 n 一定不能大於 N,否則沒完沒了。此外,在一筆測試資料中,你還需要解決 T 筆像是這樣的詢問。
請寫一支程式幫忙祺祺解決這個問題吧!
輸入的第一行有一個整數 T,代表詢問數量。
接下來 T 行每一行有三個整數 l,r,N。
請輸出 T 個數字,代表有幾個 (n,k) 滿足題目的條件。
IOICamp 2022 Day5 pB