7# mathe
:victory:
mathe可以看一下 原题，我已经追加在主题帖里了
固定数做除数，是有特殊加速算法的，可以用乘以一个固定数再右移固定位数即可，以避免除法指令。
6# wayne
这题竟然被我蒙混过关了准确的说，不是蒙混过关，而是代码很dirty，函数模块封装的不好。
应该在powMod(a,n,MOD);的里面 做 a%=MOD
12# gxqcn
哦，不解。“固定数取模” 就是 我前面说的两个数的乘积的取模吗，
老大可否再透露一点细节，
俺对大数运算，高精度计算，符号运算 还是很感兴趣的，
虽然如此，但一直没有花时间去深入的编程实践，积攒甚少。
刚才有点“笔误”，我说的是常数作被除数时有快速算法：
Unsigned division by constant
=============================
enter divisor: 10007
; dividend: register other than EAX or memory location
MOV EAX, 0x68C8C4AD
MUL dividend
SHR EDX, 12
; quotient now in EDX
IMUL EDX, 10007
SUB EAX, EDX
; remainder now in EAX
汇编呀，:(
对于M是素数还是比较简单的。先计算分子分母中M次数是否相等，如果不等答案就是0
然后分子分母分别模M相乘，但是遇上M的倍数要先将M因子全除去（而这里由于M已知，不需要每个数都判断，而是可以写成两重循环）。于是得到结果a/b(mod M)，
然后对b求数论倒数相乘即可。
divid by constant优化通常编译器自己会做
17# mathe
多谢mathe！
简直是 高屋建瓴，势如破竹啊
得空 按mathe的思路实现出来了：int extendedGCD(int a, int b, int &x, int &y)
{
/*ax+by=gcd(a,b)*/
if(b==0)
{
x=1;
y=0;
return a;
}
else
{
int s = extendedGCD(b,a%b,x,y);
int tmp=x;
x=y;
y=tmp-(a/b)*y;
return s;
}
}
int binomialMod(int k,int n,int mod)
{
int ii,tmp_k=1,tmp_n=1,g,x_k,y_mod;
for(ii=0; ii<n; ii++) tmp_k*=k-ii,tmp_k%=mod;
for(ii=1; ii<=n; ii++) tmp_n*=ii,tmp_n%=mod;
g=extendedGCD(tmp_n,mod,x_k,y_mod);
if(x_k<0) x_k+=mod;
return (tmp_k*x_k)%mod;
}