子集

Posted on In

题目大意: 给定 L, R，令 \(S[L,R]_{x}\) 表示区间 \([L,R]\)内 x 的倍数组成的集合，形式化的，我们有\(S[L,R]_{x} = {d|L ≤ d ≤ R, x|d}\)。定义一个集合的权值为这个集合中所有元素之和。那么，能否求出最小的 x，使得 \(S [L,R]_x\)有非空子集的权值和为 K 呢？虽然小 P 喜欢数学，但数学似乎并不喜欢他，所以他并不会这个问题。请你帮助小 P 解决他的问题。若无解，请输出 No Solution

10pts:直接暴力枚举

30pts:考虑当前x一定会求出对应的一个S,然后发现S中每一个元素都只会出现\(2^{|S|-1}\)个子集里面(我选了当前这个元素之后,在剩下的子集里面都可以选或者不选)因此S的价值=每一个元素*$2^{|S| - 1}\(2,也就是\)sum_S ^{|S| - 1}$

50pts:考虑当前x对应找到的S,其中一定每一个数字都是x的倍数,且一定是连续的x的倍数,再稍加分析就会得到每一个元素都是\(k \times x\)的形式其中\((\lfloor\dfrac{l-1} { x }\rfloor \leq k \leq \lfloor \dfrac {R} {x} \rfloor)\),所以\(sum_S\)就可以\(O(1)\)用等差数列求

100pts:数论分块

大致思想,对L内的分一下,对L至R内的分一下,总复杂度:\(O(\sqrt L + \sqrt {(R - L)})\)

我们枚举(l-1)/x,r/x,也就是k的范围,然后可以求出这一段的和,然后通过判断这一段的长度以及反推出x总之就是各种判断以及计算来验证合法性,然后如果发现x合理就可以取min

实在是一道数论分块不可多得的好题

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 1e4 + 66;

inline ll read()
{
    ll s(0), w(1);
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void put(ll x)
{
    if (! x) putchar('0');
    if (x < 0) putchar('-'), x = -x;
    int num(0); char c[66];
    while (x) c[++ num] = x % 10 + 48, x /= 10;
    while (num) putchar(c[num --]);
    return (void)(putchar('\n'));
}

inline void yhm_func()
{
    int L, R, K, cnt(0), ans = (1ll << 60), x, i, j, sum;
    L = read(), R = read(), K = read();
    x = K, -- L;
    while (x % 2 == 0) x /= 2, ++ cnt;

    for (i = 1, j = 0; i <= L; i = j + 1)
    {
        int l = L / i, r = R / i;
        j = min(L / l, R / r);
        if (r - l - 1 > cnt || r - l <= 0) continue;
        sum = K / (1ll << (r - l - 1)) * 2;
        if (sum % (r - l)) continue;
        x = sum / (r - l);
        if (x % (l + r + 1)) continue;
        x /= (l + r + 1);
        if (l == L / x && r == R / x) ans = min(ans, x);
    }

    for (i = L + 1, j = 0; i <= R; i = j + 1)
    {
        int l = 0, r = R / i;
        j = R / r;
        if (r - l - 1 > cnt || r - l <= 0) continue;
        sum = K / (1ll << (r - l - 1)) * 2;
        if (sum % (r - l)) continue;
        x = sum / (r - l);
        if (x % (l + r + 1)) continue;
        x /= (l + r + 1);
        if (l == L / x && r == R / x) ans = min(ans, x);
    }

    if (ans == (1ll << 60)) puts("No Solution");
    else put(ans);
    return;
}

signed main()
{	
    int T = read();
    while (T --) yhm_func();

    return 0;
}