ACM

POJ 1845 Sumdiv(唯一分解+递归二分+快速幂+大数模)

POJ 1845 	Sumdiv(唯一分解+递归二分+快速幂+大数模)
题目意思是,给出一个底数和他的幂,请计算这个数的所有因素之和。下面对四个知识点进行梳理:1、唯一分解定理:定义:任何一个大于1的自然数N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积A=p1^a1 * p2^a2 * p3^a3 *...* pn^an,这里p1<p2<p3......<pn均为质数,其中指数ai是正整数。这样的分解称为N的标准分解式。由于 A... 继续阅读 »
ACM

BZOJ-1008 越狱(排列组合+快速幂)

BZOJ-1008 越狱(排列组合+快速幂)
题意:这个是中文,不用解释了吧。因为每个人有m种宗教可以信仰,那么一共有m^n种排列情况。而不发生越狱的情况只能是,第一个人选择m的一种,第二个人有m-1种选择,后面为了不同,都是m-1种选择,共m*(m-1)^(n-1)种。由于幂太大,达到连大数都存不下了,所以这里需要用到快速幂来计算。快速幂其实就是把一个带幂的数拆分一下,幂为偶数的时候可以除一半,把底数多一个,奇数的时候先拆一个出来使幂变成偶... 继续阅读 »