CF1656D K-good

题意：

给定一个整数 \(n\)，请找出一个大于等于 \(2\) 的整数 \(k\)，使得 \(n\) 可以表示成 \(k\) 个除以 \(k\) 的余数互不相同的数之和。

注意\(k\)个除以 \(k\) 的余数互不相同的数之和这一句话。容易想到，这就相当于是对 \(k\) 的一个完全剩余系求和使得和为 \(n\)。

因为除以 \(k\) 所能得到的余数只能为 \(0\) 到 \(k - 1\)，并且，任意一个数减去余数部分，剩下的部分都可以被表示为 \(xk\)，其中 \(x\) 为整数。

因此，我们设这些余数互不相同的数的和为 \(pk + \frac{k(k - 1)}{2}=n\)。有了这个式子，我们不难想到枚举 \(k\)并将结果与 \(n\) 进行比较，自然，收获TLE。

将柿子变形，又有：

\[k(2p + k - 1) = 2n
\]

其中，\(2p\) 为偶数，\(k\) 和 \(k-1\) 各为偶数或奇数，易证， \(2n\) 为偶数，且 \(k\) 和 \((2p+k-1)\) 各有一个为奇数或偶数，且后者在题目情况中恒大于前者。

因此将 \(2n\) 进行分解，把它分解为一个 \(2\) 的次幂 \(a\) 和一个奇数 \(b\)，因此得到这个柿子：

\[k = min(a,b)
\]

AC代码：

#include<bits/stdc++.h>

#define int long long

using namespace std;

int k,n,t;

signed main(){

	cin >> t;

	while(t--){

		cin >> n;

		k = 2;

		bool flag = 0;

		int j = 1;

		n *= 2;

		while(n % 2 == 0){

			j *= 2;

			n /= 2;

		}

		if(n == 1){

			cout << "-1\n";

		}

		else{

			cout << min(n,j) << "\n";

		}

	}

}

巴特西

CF1656D K-good

题意：

AC代码：

最新文章

热门文章