锐客网

  1. 首页 > it技术 > >

K-good|K-good number Theory + 数学问题

这道题是我做CodeTon Round1时的D题，总的来看思路很重要，有几个比较明显的切入问题的角度，要选择到最优的那个；
先看题目：
K-good|K-good number Theory + 数学问题
文章图片



我们可以发现，这道题的描述一目了然，就是说我们能不能找k个数的和正好等于我们输入的n；
但是有对于这k个数的限制：
·k>=2
【K-good|K-good number Theory + 数学问题】`k[i]%k 不相同

所以我们粗略的想想就可以想到，既然这k个数的关于k的余数都不相同，且为k个正数，所以我们就可以这么想这k个数是在1，2，3……，k的基础上进行的修改（+k || +2k || +3k……），所以我们就可以得到这样一个一定正确的式子：
我们先令dp[i]为i的高斯求和，k是我们最后的ans：
if ( (n - dp[k]) % k == 0 ) ans = k;
解释一下：因为n能和这个高斯和的差能被k整除得到x，说明我只要对于1~k中的任意x个数加上一个k或者对一个数加上xk都能得到这k个数；

单看这个分析是正确的，但是这道题不能这样去做是因为n的数据范围太大了！！！如果我要得到这么dp[k]去match 10^18这个数量级的话，根据高斯求和，我起码要开10^9这么大的数组，而且还得从前往后遍历，这很明显是不正确的；

所以我们对于一个数据很大的问题我们肯定是能找到某种规律是他们普遍适用的，或者说我们能逐渐将数据缩小到一个我们可以接受的范围，而且这个缩小数据的过程也一定不能是一个一个往下缩，一般采取log级别的缩减；这是解决这种问题的总体思路；

所以我会自然而然地想到我们分成奇数和偶数，然后就可以发现，当n为奇数时，一定可以取k = 2，因为3k + 2是k取2时所能涵盖的所有数，即除了1之外的奇数；那么奇数问题解决了，我们就会去想解决偶数问题 ， 但是我很难对这些偶数进行分类，只能根据样例1猜测是不是所有的2的指数幂的数都只能输出-1；

虽然上面的两个思路都没有完整的求解出我们所要的答案，但是他对于找出正确答案是有借鉴作用的，我们先去看到之前我们得出的那个充分必要条件，并将其中的dp用高斯求和展开可得 ( n - (1+k)*k/2 ) 是k的整数倍即可，然后我们可以根据数学轻松得出n和(1+k)*k/2 是k的整数倍就行了呗，由后面那个式子可以得出k只有为奇数时，后面那个才能是k的整数倍；
然后我们再将目光聚焦到前面的n上，当n为奇数时不用想肯定是可以取2的（前面的借鉴作用），所以当n为偶数时，如果他能被k整除，就是对的，说明n不能是2的指数幂，再次证明了我们刚刚的猜想是正确的；所以我们做以下操作：
当n能被2整除时，就除以2直到n变成奇数，也就是我们这里要的k就行了；

但是问题真正解决了吗？ 如果当前的dp[k] > n本身呢？说明我们k取大了对吧，然后我们刚刚的操作相当于把n拆成了奇数k和2的指数幂x，那我们就想取x，又会发现后半部分除以x后变成（1+x）/ 2，因为x为偶数，所以这样是不行的，所以我们就想这个2这么碍眼，如果我干脆取2x，会得到（k - 1 - 2x ) / 2,我们要证明这个能整除且为非负数，因为k为奇数，1+2x为奇数，所以奇数减奇数肯定是偶数，所以一定成立，但是k一定要大于等于2x+1，就一定满足题干，所以我们发现2x< k时，dp[k] > n ,2x >k时，dp[k]一定刚好满足条件；
所以对于k>1时，我们就取最后的ans = min(k,2x);
总结：这道题很多主要是数学思想上的，很多地方需要用到猜想的方法，然后对于应付大数据的数我们就要这样类似的处理，然后我们可能一开始得不出正确答案，但是通过调整之后一定能够得出我们所要的ans；

代码：
#include
using namespace std;
typedef long long LL;
int main()
{
int t;
cin >> t;
while(t--){
LL n;
cin >> n;
LL k = 1;
while(n%2 == 0){
n/=2;
k*=2;
}
if(n == 1) cout << -1 <<'\n';
else cout << min(n,2*k) << '\n';
}
return 0;
}

    推荐阅读


    上一篇：Go|Go 语言 切片的使用(增删改查)

    下一篇：整除分块学习笔记