CPC23-4-K. 喵喵的神數 （數論 Lucas定理）

CPC23-4-K. 喵喵的神數 （數論 Lucas定理）

喵喵的神?數 Time Limit: 1 Sec Memory Limit: 128 MB

Description
喵喵對組合數比較感興趣，並且對計算組合數非常在行。同時為了追求有後宮的素質的生活，喵喵每天都要研究
質數。

我們先來復習一下什麼叫做組合數。對於正整數P、T

然後我們再來復習一下什麼叫質數。質數就是素數，如果說正整數N的約數只有1和它本身，N就是質數；另外，
1不是質數。
今天，喵喵想要知道

Input
輸入第一行是一個整數N（N<=1000）。
接下來N行，每行包括一個正整數T和一個質數P（1<=P<=T<231）。
Output
包括N行，根據輸入的順序，每一行為一個整數：
Sample Input
2
3 2
10 3
Sample Output
1
0
HINT
Source
CPC3

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PGJyPgo8L3A+CjxwPr3izOLLvMK3o7o8L3A+CjxwPtXizOLKx7S/yv3Rp8zio6ywpqOsyv3Rp77NysfTssnLsKGjobjjwcuw68zso6zDu9PQveG5+6Osufu2z7DZtsjBy9K7z8KjrL3hufvL0bW9wcuyu8P3vvXA+rXETHVjYXO2qMDto6y+3cu1ysfXqMPFveK+9kMobiwgbSklcLXEo6zG5NbQcMrH1srK/aGjPC9wPgo8cD5MdWNhc7aowO3Q8Mr2yOfPwqO6PC9wPgo8cD48L3A+CiAgICAgICAgyv3C20x1Y2FztqjA7crH08PAtMfzIGMobixtKSBtb2QgcLXEJiMyMDU0MDsscMrHy9jK/aOotNNuyKFt1+m6z6OsxKPJz3CjqaGjCgrD6Mr2zqo6CgpMdWNhcyhuLG0scCk9Y20obiVwLG0lcCkqIEx1Y2FzKG4vcCxtL3AscCkKCkx1Y2FzKHgsMCxwKT0xOwoKCrG+zOLW0KOsyMPH87XEysc8aW1nIHNyYz0="https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017012113492492.jpg" alt="\">,所以，n = p, 代入得 Lucas(n,m,p) = cm(n%p, m%p)* Lucas(n/p, m/p, p) = cm(n%p, p%p)* Lucas(n/p, p/p, p) = cm(n%p, 0)* Lucas(n/p, 1, p) = 1 * Lucas(n/p, 1, p) = C(n/p, 1) % p = C(n/p, 1) % p = ( n/p ) % p

AC代碼：

#include 
#include 
using namespace std;

int main(){
	freopen("in.txt", "r", stdin);
	int n, t, p;
	cin >> n;
	while(n--){
		cin >> t >> p;
		cout << (t / p) % p << endl;
 	}
 	return 0;
}