为何超时 --java D题

BigInteger b1 = new BigInteger(next());
BigInteger b2 = new BigInteger(next());
out.println(b2.gcd(b1.mod(b2)));
全部评论
Java中大数BigInteger类的gcd方法底层是欧几里得算法 理论上是最优算法   时间复杂度为O((log(max(a, b)))^2) 但是 BigInteger的运算需要考虑到操作数的位数,特别是在位数相差较大时,性能可能稍有影响。 如果两个大整数 a 和 b 的位数相等,那么时间复杂度可以接近 O(log(a)),其中 a 是位数。 如果两个大整数的位数不相等,BigInteger会执行多次模运算和移位操作来逐步减小问题规模,这些操作可能需要多次迭代,导致时间复杂度稍微增加。 你看题目 a是大数 b是32位
2 回复 分享
发布于 2024-07-14 21:07 吉林
我觉得他这么出题就是为了卡Java...
1 回复 分享
发布于 2024-07-14 21:14 吉林

相关推荐

2025-11-28 13:56
已编辑
门头沟学院
所有好工作吻上来:最近可能压力比较大吧,面试的时候已经不屑于去说一些违心的话了,今天这场面试我真是没控制住啊,感觉我已经要发火了
实习学到最有价值的工作习...
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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