模与差题解

不妨设x<y,可以发现,如果知道了nx%y是多少,那么接下来[nx,nx+x-1]的和就可以O(1)计算。
采用这个方法,最终复杂度是O(n/x)的。
但是我们发现,如果nx=lcm(x,y),那么就会产生循环节,便可以不用重复计算,O(1)产生后面的答案。
因此最坏复杂度是O(max(x,y))的,在gcd(x,y)=1的情况下。

全部评论

相关推荐

爱吃烤肠的牛油最喜欢...:50K是ssp了估计,ssp的人家多厉害都不用说,每年比例大概在百分之5左右
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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