词条 | lucas |
释义 | 3 俄罗斯名模纳塔利-沃佳诺娃之子纳塔利·沃佳诺娃(Natalia Vodianova),俄罗斯著名模特,1982年出生在俄罗斯,16岁时在水果摊打工被星探发掘,之后就像灰姑娘变成了公主一样,走向了成功。 2001年,纳塔利-沃佳诺娃19岁,邂逅富有、英俊的英国贵族贾斯汀-波特曼(Justin Portman),同年生下第一个儿子Lucas。19岁结婚生生子对于一个模特来说,很可能就意味着职业生涯的终结。可是Natalia在生下儿子Lucas后的第6个星期就重新回到了T型台上。2002年,纳塔利-沃佳诺娃与贾斯汀-波特曼举行盛大婚礼。 纳塔利-沃佳诺娃的丈夫贾斯汀-波特曼,来自英国显赫的贵族之后——已故英国子爵Edward Henry Berkeley Portman 的第三个儿子。 5 数论定理数论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; } |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。