题解 P1372 【又是毕业季I】

By lzn 数论水题一道。 首先，若可能的最大公约数为a，取出的k个数为X1，X2，……，Xk且满足X1<X2<……<Xk，那么有X1>=a，X2>=2a，……，Xk>=ka。又∵Xk<=n，∴n>=ka，∴a<=n/k，又∵a为整数，∴a<=[n/k]（[]为取整符号）。 另一方面，我们取[n/k]，2\*[n/k]，……，k\*[n/k]，它们的最大公约数a=[n/k]，且它们都小于等于n大于等于1，且互不相等，满足条件。 ∴答案即为[n/k]。 算法复杂度o(1)