今下午学习了四种组合数,听的真的挺懵逼的,尤其是最后一种,关于a!中的质因数的分解式子
想了好久,现在也是懵懵懂懂,在这里尝试写一下最后一种组合数的思路吧
举个例子,6!=1 * 2 * 3 * 4 * 5 * 6
先用筛法筛出6内的质数分别是primes[0]=2,primes[1]=3,primes[2]=5
现6/primes[0]=3,表示质数2的倍数在1~6内有三个数分别是:2,4,6
6/primes[0]^2=1, 4
6/primes[0]^3
所以质数2在1~6内的数中分解质因数共出现4次
6/primes[1]=2,表示质数3的倍数在1~6内有三个数分别是:3, 6
6/primes[1]^2=0,
所以质数3在1~6内的数中分解质因数共出现2次
6/primes[2]=1,表示质数5的倍数在1~6内有三个数分别是: 5
6/primes[2]^3=0
所以质数5在1~6内的数中分解质因数共出现1次
所以2^4 * 3^2 * 5^1=720=6!
还有本题中的高精度乘法也很神奇,之所以能完成这些乘法是因为中间桥梁是t进位