分治|快速乘(模板)
快速乘和快速幂原理一样
主要用于是64bit整数乘法时会爆longlong但是写高精度又太麻烦的情况
代码
#include#define ll long longusing namespace std;
inline ll ksc(ll a, ll b, ll mod){
ll ans = 0;
while( b > 0 ){
if( b&1 ) ans = (ans + a) % mod;
a = ( a + a ) % mod;
b >>= 1;
}
return ans;
}
【分治|快速乘(模板)】还有一种用 long double 优化的代码
inline ll ksc(ll x, ll y, ll mod)
{
return ( x * y - (ll) ( (long double) x / mod*y )*mod + mod ) % mod;
}
推荐阅读
- 北陸的雪
- 排序(归并排序)
- 第一次组织同学们乘车
- neo4j|neo4j cql语句 快速查询手册
- 我愿乘风破浪,踏遍鸟语花香
- 通过复盘快速成长(附模板)
- 江苏客谈鬼
- jar|springboot项目打成jar包和war包,并部署(快速打包部署)
- 快速阅读作业【2/21】《阅读(革命性新定义》)
- Spring注解05|Spring注解05 @Import 给容器快速导入一个组件