@谢振轩 谢霆锋、张柏芝之子

@卢卡斯 中国电视剧《败犬女王》中的角色

3 俄罗斯名模纳塔利-沃佳诺娃之子

@小辉 《宠物小精灵》中人物

5 数论定理

纳塔利·沃佳诺娃（Natalia Vodianova），俄罗斯著名模特，1982年出生在俄罗斯，16岁时在水果摊打工被星探发掘，之后就像灰姑娘变成了公主一样，走向了成功。

2001年，纳塔利-沃佳诺娃19岁，邂逅富有、英俊的英国贵族贾斯汀-波特曼（Justin Portman），同年生下第一个儿子Lucas。19岁结婚生生子对于一个模特来说，很可能就意味着职业生涯的终结。可是Natalia在生下儿子Lucas后的第6个星期就重新回到了T型台上。2002年，纳塔利-沃佳诺娃与贾斯汀-波特曼举行盛大婚礼。

纳塔利-沃佳诺娃的丈夫贾斯汀-波特曼，来自英国显赫的贵族之后——已故英国子爵Edward Henry Berkeley Portman 的第三个儿子。

数论Lucas定理是用来求 c(n,m) mod p的值,p是素数（从n取m组合，模上p）。

描述为:

Lucas(n,m,p)=cm(n%p,m%p)* Lucas(n/p,m/p,p)

Lucas(x,0,p)=1;

而

cm(a,b)=a! * (b!*(a-b)!)^(p-2) mod p

也= (a!/(a-b)!) * (b!)^(p-2)) mod p

这里，其实就是直接求 (a!/(a-b)!) / (b!) mod p

由于 (a/b) mod p = a * b^(p-2) mod p

◎ C语言代码实现

#include "stdio.h"

typedef __int64 lld;

int N,M,P;

int Pow(lld a,lld n,lld p)

{

lld x=a;

lld res=1;

while(n)

{

if(n&1)

{

res=(res*x)%p;

}

n>>=1;

x=(x*x)%p;

}

return res;

}

int Cm(lld n,lld m,lld p)

{

lld a=1,b=1;

if(m>n)return 0;

//实现(a!/(a-b)!) * (b!)^(p-2)) mod p,由于n比较大，所以，此处不知道有什么好的优化

while(m)

{

a=(a*n)%p;

b=(b*m)%p;

m--;

n--;

}

return (a*Pow(b,p-2,p))%p;

}

int Lucas(lld n,lld m,lld p)

{

if(m==0)

return 1;

return (Cm(n%p,m%p,p)*Lucas(n/p,m/p,p))%p;

}

int main()

{

int t;

//freopen("in.txt","r",stdin);

scanf("%d",&t);

while(t--)

{

scanf("%d%d%d",&N,&M,&P);

printf("%d\",Lucas(N,M,P));

}

return 0;

}