模与差题解

不妨设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的情况下。

全部评论

相关推荐

牛客62533758...:华为不卡双非,而是卡院校hhhh
点赞 评论 收藏
分享
04-01 16:02
已编辑
武汉工程大学 Java
沉淀小子:不太懂你强调第一次面的意思,感觉没必要强调,有面试就去面,少搞点焦虑
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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