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;
}
全部评论

相关推荐

点赞 评论 收藏
分享
夏目LTH:这个真的很看运气,多投吧。我从去年十二月底一直投到现在,之前没一个offer,结果两周前投的一家面试官聊的特别好,直接速通offer还给的SP待遇开的比我期望都够。
我的求职进度条
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务