模与差题解
不妨设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的情况下。
2021-04-01 12:42 已编辑 西北农林科技大学
关注
全部评论
相关推荐
05-13 10:36
门头沟学院 计算机类 
字节跳动开奖32人在聊 点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
点赞 评论 收藏
转发
