HBC217463小乐乐与序列,排序,枚举,离散化小G的GCD题解

冷默言语算法基础篇 2023-11-14 07:56:02 86 0

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

小G刚学习完辗转相除法求GCD，现在他想探究一下辗转相除具体的次数，然后写出了如下代码： long long GCD {

小G刚学习完辗转相除法求GCD，现在他想探究一下辗转相除具体的次数。然后写出了如下代码： long long GCD(long long x, long long y) { if (!y) return 1ll; return GCD(y, x % y) + 1ll; } 现在小G很好奇一个问题，他想求一下maxGCD 小G接着写出了以下代码： long long maxGCD(long long n) { long long ans = 0ll; for (long long i = 1; i <= n; i++) for (long long j = 1; j <= n; j++) ans = max(ans, GCD(i, j)); return ans; } 但是这个代码太慢了，小G会给出一个n{n}n，希望你帮他快速求出答案。