首页 > 代码库 > HDU 3304 Interesting Yang Yui Triangle lucas定理
HDU 3304 Interesting Yang Yui Triangle lucas定理
输入p n 求杨辉三角的第n+1行不能被p整除的数有多少个
Lucas定理:
A、B是非负整数,p是质数。AB写成p进制:A=a[n]a[n-1]...a[0],B=b[n]b[n-1]...b[0]。则组合数C(A,B)与C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0]) mod p同余
即:Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p),在存在i,b[i]>a[i]时,mod值为0,所以必定整除;当对于所有i,b[i]<=a[i]时,a[i]!%p!=0,所以必定不能整除
#include <cstdio> #include <cmath> #include <cstring> using namespace std; int main() { int p, n; int cas = 1; while(scanf("%d %d", &p, &n) != EOF) { if(p ==0 && n ==0) break; int sum = 1; while(n) { sum *= n%p+1; n /= p; } printf("Case %d: %04d\n", cas++, sum%10000); } }
HDU 3304 Interesting Yang Yui Triangle lucas定理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。