【CF1656D】K-good题解

lzytag · 2022-03-25 13:59:19 · 题解

题解

题目传送门

做法

众所周知，这场比赛 D < E 。

首先，我们来考虑一下 k-good 数满足什么条件。

很显然，分 k 为奇数和偶数讨论。

• 当 k 为奇数时，n \equiv 0 \mod k。
• 当 k 为偶数时，n \equiv \frac{k}{2} \mod k。
• 无论 k 的奇偶性，n \ge \frac{k \times (k - 1)}{2}。

知道了以上三点性质，我们就可以没有思路开始坐牢继续往下想了。

很明显，k 为偶数是的条件更容易满足，我们同时可以想到一个式子，可以将任意整数 n 表示为 2^a \times b (b \equiv 1 \mod 2,a \ge 0)

很明显，他似乎可以满足 2^{a+1}-good 的性质。

但是，我们不能保证它满足第三个性质。

我们同时发现，它可以满足b - good 的性质

于是可以分类讨论

• 当2^{a+1}+1 \ge b，答案为 b。
• 反之，答案为 2^{a+1}

最后，如果 b 为 1 呢？

很明显，这时无论 k 实际还是偶，都不满足条件，答案为 -1。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
int read()
{
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
ll lread()
{
    ll x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) f|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
//file head over
void solve()
{
    ll n = lread(),tmp = 1;
    while(n%2 == 0)
    {
        n /= 2;
        tmp *= 2;
    }
    if(n == 1)
    {
        puts("-1");
        return ;
    }
    if(tmp*2+1 <= n) printf("%lld\n",tmp*2);
    else
    {
        printf("%lld\n",n);
    }
}
int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}