O(1)快速乘

求两个数相乘并取模,但是乘积超过了long long怎么办呢?

一般都是快速幂的思想快速乘,时间复杂度为log(n)很快了,这里提供一个更快的O(1)算法

inline long long multi(long long x,long long y,long long mod)
{
	long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
	return tmp<0 ? tmp+mod : tmp;
}
全部评论

相关推荐

11-26 22:34
已编辑
重庆邮电大学 Java
快手 客户端开发 (n+5)k*16 公积金12
牛客895077908号:佬 什么双非硕啊
点赞 评论 收藏
分享
粗心的雪碧不放弃:纯学历问题,我这几个月也是一直优化自己的简历,后来发现优化到我自己都觉得牛逼的时候,发现面试数量也没有提升,真就纯学历问题
点赞 评论 收藏
分享
10-29 15:38
门头沟学院 Java
榕城小榕树:难道你简历里写了配送路径优化算法?
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务