K God

 

https://codeforces.com/contest/1656/problem/D

极为简单,却未能想出。重点记录

题意

给定一个整数 n 求是否能够用 $k$ 个模 k 不同的数组成一个该数。

思路

我们发现对于这 n 个数而言,可以简单的缩略成一个式子。

\[n = ks + \frac {k*(k + 1) }{2} \\ 2 \times n = k\times(k + 2s + 1)\]

我们发现等式的右边变为两个数,一个是 k 另一个是 k 加上一个奇数。也就是说,可以将 2n 划分为 一个偶数×奇数的情况。

不难想到,如果我的 n 是一个 $2^i$ 形式的数字的话,那么我们的等式一定不能成立。

因此我们只需要把 2n 中的 $2^i$ 抽出来即可解决这个问题。

也就是说我把我的答案划分为诸如 $2^i\times x$ 的形式 $x$ 一定是奇数。

此时我们只需要取 $\min {2^i , x}$ 即为答案。

code

algorithm