数学技巧

题目

题目

• 越狱 典

  \(简析\) 既然顺着题目想 很困难, 是否可以 "逆向"思维?

  ​ 答案为: \(m^n - m(m-1)^{n-1}\)

  AC代码 注意: \((a-b)\bmod p\) 在实现上应写成 \((a-b+p)\bmod p\)

快速幂

求 \(a^b\) . 　由于 \(b=c_{k-1}2^{k-1} + c_{k-2}2^{k-2}+...+c_02^0\), 其中 \(k=\lceil log(b+1)\rceil\)​(b在二进制下的位数)

我们可以递推.

int qpow(int a, int b){
    a%=MOD;							// 别漏了~
	int res=1;
	while(b){
		if(b&1) res=(res*a)%MOD;	// 若MOD略大, 这里可能需要转 long long
		a=(a*a)%MOD; b>>=1;
	}
	return res;
}

速乘

由于乘法可能会爆 long long, 比如 快速幂中的乘法, 如果 MOD很大(比如为INT_MAX) 就很有可能爆long long.
写 高精度? 太麻烦了, 不仅容易出错, 还效率很低. 　　
于是有了如下两个速乘: 龟速乘和快速乘

龟速乘 \(O(log\ b)\)

与快速幂原理大同小异.

ll smul(ll a, ll b, ll P){
    ll res=0;
    while(b){	
		if(b&1) res=(res+a)%P;
        a=(a+a)%P; b>>=1;
    }
    return res;
}

快速乘 \(O(1)\)

核心为: \(ab\bmod p = ab-\lfloor ab/p\rfloor p\)​ 　记 \(c=\lfloor ab/p\rfloor\)​

• 求 c: 用 浮点数直接计算 \(ab/p\), 当浮点数精度不足以保存精确数值时, 它会舍弃低位.

  而 long double 在十进制下的有效数字为 18~19 位, 而 若 \(a,b<p\)​​ 则 c 也在18位以内. 可以用long double 来存 c

• 值得一提的是: 若 \(p\mid ab\)​ , 则由于精度误差, 算出的c可能比实际小1, 但在取模意义下并不影响结果的正确性

• 由于\(ab-cp = ab\bmod p\)​, 且\(ab-cp≤p<2^{64}\) 所以\(ab-cp=(ab-cp)\bmod 2^{64}\) !

  用unsigned long long的自然溢出进行模数

ull qmul(ull a, ull b, ull p){
	a%=p, b%=p;
    ull c=(long double) a*b/p
    ull x=a*b, y=c*p;
    ll res=(ll)(x%p) - (ll)(y%p);	//这里的括号不要漏掉了
    if(res<0) res+=p;				//不要漏掉了.
    return res;
}