K-good

Created by LXC on Wed Apr 10 12:38:24 2024

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

ranting: 1900

tag: constructive algorithms, math, number theory

problem

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

数据范围：

• $t$ 组数据，$1\leqslant t\leqslant 10^5$。
• $2\leqslant n\leqslant 10^{18}$。

Translated by Eason_AC

solution

这k个数之和，可以表示为$t\times k+ \sum \limits_{i=0}^{k-1} i = n \Rightarrow t\times k+ \frac{k(k-1)}{2} = n \Rightarrow k(k+2t-1) = 2n$，由于k个数是正整数，$t>0$。

如果$2n$含奇数因子，令奇数因子为$u$，$v=n/u$。由于$k$与$k+2t-1$奇偶性不同，且$k+2t-1\ge k$。
当$u > v$时，$u = k+2t-1, v = k$
当$u < v$时，$v = k+2t-1, u = k$.

所以答案就是$\min(u,v)$

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    ll n;
    cin >> n;
    ll a = 2*(n&-n), b = n/(n&-n);
    // cout << n << " " << a << " " << b << endl;
    if (min(a, b) == 1) {
        cout << "-1\n";
    } else {
        cout << min(a, b) << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}