一些奇怪的但关键时刻派的上用场的算法

2021-02-05 06:16

阅读：640

标签：常用快速乘优化正确答案 lang 防止答案 line mat

龟速乘

能有效防止运算时爆long long的一种神奇的算法。

直接背就好，常用。

ll ksc(ll a, ll b, ll mod){
    ll ans = 0;
    for(;b; b >>= 1, a = (a + a) % mod) 
        if(b&1) ans = (ans + a) % mod;
    return ans;
}

这个东西最初我感觉很不靠谱，但它就是能算出来正确答案。它就是用 \(long\ double\)来进行优化取模运算。

inline ll ksc(ll x,ll y,ll p){
	ll z=(ld)x/p*y;
	ll res=(ull)x*y-(ull)z*p;
	return (res+p)%p;
}

一些奇怪的但关键时刻派的上用场的算法

标签：常用快速乘优化正确答案 lang 防止答案 line mat

原文地址：https://www.cnblogs.com/iloveori/p/12790937.html

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：一些奇怪的但关键时刻派的上用场的算法
文章链接：http://soscw.com/index.php/essay/51211.html

亲，登录后才可以留言！