CF 1656D K-good(思维)

本文最后更新于：3 years ago

题目链接:点击跳转
题意： 给你一个数n(2 <= n <= 1e18), 问n是不是k-good数(及分成k个数，k个数的和为n，这k个数取模k的结果均不相同),如果存在多个k成立，输出任意一个即可

思路：

  • 如果一个数能被拆成一个奇数和一个偶数的积(奇数不能为1)，该数就是k-good数。
  • 取奇数个，如40 = 5 * 8， 取中间数为8，剩余的数可以依次改为 6 7 9 10。 取偶数个， 如102 = 6 * 17， 则中间数为 8 9，两边依次为3 4 5 6 7 10 11 12 13 14，及分成奇数个就将偶数作为中心，偶数个就将奇数拆成两个(差为1的两个数)，然后剩下的数均能分成两边补在两边，而连续的数字，在取模数量的时候，一定是刚好一个数字一个位置，及不会在取模下出现重复。
  • 那么要怎么拆呢，可以直接将输入的n一直除2，直到n为奇数， 同时记录除掉的部分，那么就得到我们所需要的n * k = 原数

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
#include <ostream>

using namespace std;
typedef long long ll;
#define endl '\n'
typedef pair<int, int> PII;
#define debug() cout.flush()
#define for0(i, a) for (int i = 0; i < a; ++i)
#define REP(i, a, b)  for (int i = a; i < b; ++i)
#define FOR(i, a, b)  for (int i = a; i <= b; ++i)
#define REPC(i, a, b, c)  for (ll i = a; i < b && i < c; ++i)
#define RREP(i, a, b) for (int i = a; i >= b; --i)
const ll MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int MAXN = 3e5 + 5e5;

inline void init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

inline void solve() {
    int _;
    cin >> _;
    while (_--) {
        ll n;
        cin >> n;
        ll tmp = 1;
        while (!(n & 1)) {
            n >>= 1;
            tmp <<= 1;
        }
        cout << (n == 1 ? -1 : min(n, tmp << 1)) << endl;
    }
}

signed main() {
    init();
    solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
def solve():
    _ = int(input())
    for i in range(_):
        n = int(input())
        tmp = 1
        while n & 1 == 0:
            n >>= 1
            tmp <<= 1
        print(-1 if n == 1 else min(n, tmp << 1))

if __name__ == '__main__':
    solve()