K-good（数论/取模运算/构造）

题目 题意：给定一个数 n < = 1 e 18 n=2 k>=2，使得 n n n可以由 k k k个 模 k k k意义下各不相等的正整数相加得到。 参考 思路：题意转化为给定 n n n，是否存在 k k k，使得 n = = k ∗ ( k + 1 ) / 2 + k ∗ x n==k*(k+1)/2+k*x n==k∗(k+1)/2+k∗x，其中 x > = 0 x>=0 x>=0。 k k k个数在模 k k k意义下取值为 1 , 2 , . . . , k − 1 , k 1,2,...,k-1,k 1,2,...,k−1,k，它们相加后为 k ∗ ( k + 1 ) / 2 k*(k+1)/2 k∗(k+1)/2，再加上若干个 k k k，即得到上式。 所以 n n n要满足两个条件：

• n > = 1 + 2 + . . . + k = k ∗ ( k + 1 ) 2 n>=1+2+...+k=\frac{k*(k+1)}{2} n>=1+2+...+k=2k∗(k+1)​
• n = k ∗ ( k + 1 ) 2 ( % k ) n=\frac{k*(k+1)}{2}(\%k) n=2k∗(k+1)​(%k) 当 k k k为偶数时，上述第二式可以简化为 n = k 2 ( % k ) n=\frac{k}{2}(\% k) n=2k​(%k)，该式成立，当且仅当 2 ∗ n 2*n 2∗n是 k k k的倍数，而 n n n不是 k k k的倍数。且我们应该取最小的 k k k，为满足第一式，此时 k k k取 k 1 = 2 p + 1 k1=2^{p+1} k1=2p+1，其中 p p p为 n n n能整除2的最大次数。 假如 k 1 k1 k1能满足第一式，则可以得到答案。 如果 k 1 k1 k1不满足第一式，考虑 k 2 = 2 ∗ n k 1 k2=\frac{2*n}{k1} k2=k12∗n​，根据 k 1 k1 k1的性质（ 2 ∗ n 2*n 2∗n是 k 1 k1 k1的倍数，而 n n n不是 k 1 k1 k1的倍数），可得 k 2 k2 k2为奇数，且此时由 k 1 ∗ ( k 1 + 1 ) > 2 ∗ n = > k 2 < k 1 + 1 = > k 2 < = k 1 − 1 k1*(k1+1)>2*n=>k2k22∗n=>k2k2