Znzryb's Blog
0%

Posted on Edited on

题目大意

题目描述
给定一个整数 nn，要求找到最小的正整数 kk，使得 nn 能够整除 knk^n（即 nn 是 knk^n 的因数）。
数据保证在给定范围内始终存在答案。

输入格式
第一行包含一个整数 tt（1≤t≤1001 \le t \le 100），表示测试用例的数量。
接下来的 tt 行，每行包含一个整数 nn（2≤n≤1092 \le n \le 10^9），表示题目给定的数值。

输出格式
对于每个测试用例，输出一行一个整数，表示满足条件的最小正整数 kk。

样例输入

1
2
3
4
5
4
8
12
369
55635800

样例输出

1
2
3
4
2
6
123
2090

样例解释
在第一个测试用例中（n=8n = 8）：
当 k=1k = 1 时，18=11^8 = 1，88 不是 11 的因数；
当 k=2k = 2 时，28=2562^8 = 256，88 是 256256 的因数（因为 256=8×32256 = 8 \times 32）。
因此，最小可能的 kk 为 22。

在第二个测试用例中（n=12n = 12）：
最小的 kk 为 66，因为 1212 是 612=21767823366^{12} = 2176782336 的因数（因为 2176782336=12×1813985282176782336 = 12 \times 181398528）。

思路讲解

不难发现，答案就是 N 的所有素因子的乘积。

不过对于我来说，一个难点是怎么样求，就是N的所有素因子的乘积是多少。（在这道题目的数据范围限制下）

我们这里就用到了一个小trick，就是一个数啊，大于根号N的素因子，有的话只有一个。因此我们就不断的把小的素因子全部都给除掉，那么剩下的一个素因子就是最大的了。（而且这个大于根号N的素因子显然不可能被乘很多遍）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll opN=N;
for (auto p1:primes) {
    if (p1*p1>N) {
        break;
    }
    if (opN%p1==0) {
        res*=p1;
        while (opN%p1==0) {
            opN/=p1;
        }
    }
}
res*=opN;
cout<<res<<"\n";

AC代码

AC

https://codeforces.com/contest/2205/submission/364837938

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目大意

Alice 和 Bob 在玩一个游戏。给定两个数组：包含 nn 个元素的数组 aa 和包含 mm 个元素的数组 bb。

两人轮流进行操作，Alice 先手。在每个回合中，玩家需要从数组 aa 中选择一个数字 xx，并从数组 bb 中选择一个数字 yy。

  • Alice 的规则：选择的 yy 必须能被 xx 整除。

  • Bob 的规则：选择的 yy 必须不能被 xx 整除。

选定 xx 和 yy 后，yy 会从数组 bb 中被移除（如果数组中存在多个相同的 yy，只移除其中一个），而 xx 仍然保留在数组 aa 中。无法进行合法操作（即无法选出满足自身规则的 xx 和 yy）的玩家将输掉游戏。

假设双方都采取最优策略，请判断谁会赢得游戏。

输入格式

第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例的数量。

对于每个测试用例：
第一行包含两个整数 nn 和 mm（1≤n,m≤1061 \le n, m \le 10^6）。
第二行包含 nn 个整数 aia_i（1≤ai≤n+m1 \le a_i \le n+m），表示数组 aa 的元素。
第三行包含 mm 个整数 bib_i（1≤bi≤n+m1 \le b_i \le n+m），表示数组 bb 的元素。

保证所有测试用例中 nn 的总和以及 mm 的总和均不超过 10610^6。

输出格式

对于每个测试用例，输出获胜者的名字：如果 Alice 赢，输出 Alice；如果 Bob 赢，输出 Bob。

样例输入

1
2
3
4
5
6
7
8
9
10
3
9 3
3 2 4 2 2 4 4 2 4
6 7 12
10 3
3 2 5 4 2 5 3 4 4 4
10 7 13
1 5
1
1 2 3 4 5

样例输出

1
2
3
Alice
Bob
Alice

样例解释

对于第一个测试用例，Alice 的获胜过程如下：

  1. Alice 的回合：选择 x=3,y=6x=3, y=6（66 能被 33 整除）。操作后 66 从数组 bb 中移除，此时 b=[7,12]b=[7, 12]。

  2. Bob 的回合：选择 x=3,y=7x=3, y=7（77 不能被 33 整除）。Bob 在这个回合只能选择 y=7y=7，因为对于 y=12y=12，数组 aa 中找不到任何不能整除它的 xx。操作后 77 从数组 bb 中移除，此时 b=[12]b=[12]。

  3. Alice 的回合：选择 x=4,y=12x=4, y=12（1212 能被 44 整除）。操作后 1212 从数组 bb 中移除，此时数组 bb 变为空。

  4. Bob 的回合：数组 bb 已经为空，Bob 无法进行任何操作，因此 Bob 输掉游戏，Alice 获胜。

思路讲解

OK，我们说回来。这个D为什么交了5发还是没过呢？主要是因为就是这个D，它的数据量比较大。使用Victor victor或者victor的这种调和级数写法呢，它这个时间会超。可以使用vis 数组标记所有 a 的倍数。这样子可以避免卡常。

1
2
3
4
5
6
7
8
9
10
ll cnt_un_divide=0,cnt_all_divide=0;
vector<char> vis(N+M+2);
for (auto a:A) {
    for (ll i=1;i<=N+M;++i) {
        if (i*a>N+M) {
            break;
        }
        vis[i*a]=true;
    }
}

然后为什么标题里面提了不要用 while 循环？是因为涉及累加的逻辑（在 D 的对拍暴力程序当中），直接 continue 以后，while 循环的这个累加就崩掉了。

AC代码

AC
https://codeforces.com/contest/2203/submission/364454955

心路历程（WA，TLE，MLE……）

image

后面还被系统测试阴了一手，把这个LCM改成128，用INT128就可以了，这个叫什么，当时其实我就知道这里应该是会有点问题的，想用这个128嘛，但是可能还是犹豫还是犹豫了。

1
2
3
4
i128 lcm128(i128 a,i128 b) {
    i128 res=a*b/__gcd(a,b);
    return res;
}

Posted on Edited on

题目大意

https://codeforces.com/contest/2203/problem/E

题目描述

Alice 和 Bob 有一个初始为空的牌堆。游戏共进行 mm 回合，在第 ii 回合中，会发生以下事件：

  1. 一张数值为 aia_i 的牌被加入牌堆（保证加入的牌数值各不相同）。

  2. 如果牌堆中的牌数少于 33 张，该回合直接结束。

  3. 否则，Alice 从牌堆中选择一张牌，设其数值为 aa。

  4. 接着，Bob 在知道 Alice 选了哪张牌的情况下，从剩下的牌中选择一张牌，设其数值为 bb（b≠ab \neq a）。

  5. 最后，从剩下的 i−2i-2 张牌中等概率随机抽取一张牌，设其数值为 cc。

  6. 回合结束后，这三张牌被放回牌堆。

得分规则

在确定了 a,b,ca, b, c 的值后，Bob 的得分按以下规则计算：

  • 如果 ∣a−c∣≤∣b−c∣|a - c| \le |b - c|，Bob 得 00 分；

  • 如果 cc 的值严格介于 aa 和 bb 之间（即 a<c<ba < c < b 或 b<c<ab < c < a），Bob 得 00 分；

  • 其他情况下，Bob 得分为 ∣b−c∣|b - c|。

游戏目标

在每回合中，Alice 的目标是最小化 Bob 的期望得分，而 Bob 的目标是最大化他的期望得分。两人均采取最优策略。（注意：两人是根据真实期望得分来做最小化或最大化的决策，而非取模后的值）。

输入格式

第一行包含一个整数 mm（3≤m≤2⋅1053 \le m \le 2 \cdot 10^5），表示回合数。
第二行包含 mm 个整数 a1,a2,…,ama_1, a_2, \dots, a_m（1≤ai≤10121 \le a_i \le 10^{12}，所有 aia_i 互不相同），表示每回合加入牌堆的牌的数值。

输出格式

输出 m−2m-2 个整数，第 ii 个数表示在第 i+2i+2 回合中，双方在最优策略下 Bob 的期望得分对 998244353998244353 取模后的结果。

样例 1

1
2
3
4
5
6
7
8
Input:
5
1 10 3 11 7

Output:
0
499122177
665496236

样例 1 解释

这三个输出分别对应第 3,4,53, 4, 5 回合。真实的期望得分依次为 0,12,230, \frac{1}{2}, \frac{2}{3}。

样例 2

1
2
3
4
5
6
7
8
9
Input:
6
23 7 11 24 10 28

Output:
0
499122177
1
748683266

样例 2 解释

这四个输出分别对应第 3,4,5,63, 4, 5, 6 回合。真实的期望得分依次为 0,12,1,540, \frac{1}{2}, 1, \frac{5}{4}。

样例 3

1
2
3
4
5
6
7
8
9
10
11
12
Input:
9
4 10 7 1 16 5 9 12 2

Output:
0
499122178
2
499122178
798595484
831870296
427819010

样例 3 解释

真实的期望得分依次为 0,32,2,32,85,116,1170, \frac{3}{2}, 2, \frac{3}{2}, \frac{8}{5}, \frac{11}{6}, \frac{11}{7}。

思路讲解

通过模拟，我们发现，首先，选了 A 的位置以后，B 其实只有两种选择，B 必须紧紧挨着 A 选。

然后，我们就是要确定这个 A 的选择。我们可以采用一种二分两次的方法（我自己瞎想的）。或者你也可以三分。

image

图中的 res 就是使用树状数组查询的蓝色部分的这个查询结果。

核心的这个做法这个 lambda 是这个东西，他能够在知道目前长度的情况下，求解出这个答案。

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
    auto find_ans = [&](ll len) -> ll {
        ll l = 0, r = len - 1;
        auto cal_left = [&](ll ia) -> ll {
            ll pa = processing_pos[ia];
            if (ia <= 2) {
                return 0;
            }
            ll res = tr.query(1, processing_pos[ia - 2]);
            ll pb = processing_pos[ia - 1];
            res = li_pos_to[pb].val * (ia - 2) - res;
            return res;
        };
        auto cal_right = [&](ll ia) -> ll {
            if (ia >= len - 1) {
                return 0;
            }
            ll pa = processing_pos[ia];
            ll pb = processing_pos[ia + 1];
            ll res = tr.query(processing_pos[ia + 2], N);
            res = res - li_pos_to[pb].val * (len - ia - 1);
            return res;
        };
        auto check1 = [&](ll p) -> bool {
            // 这个程序，只要左边比右边大，就 return false
            return cal_left(p) >= cal_right(p);
        };
        auto check2 = [&](ll p) -> bool {
            // 这个程序，只要左边比右边大，就 return false
            return cal_left(p) <= cal_right(p);
        };
        while (l < r) {
            ll mid = l + r >> 1;
            if (check1(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        ll ans1 = l;
        l = 1, r = len;
        while (l < r) {
            ll mid = l + r +1 >> 1;
            if (check2(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        ll ans2=l;
// #ifdef LOCAL
//         debug(ans1);
//         debug(ans2);
//         debug(cal_left(ans1));
//         debug(cal_right(ans2));
// #endif
        ll res=min(max(cal_left(ans1),cal_right(ans1)),max(cal_right(ans2),cal_left(ans2)));
        res%=mod;
        res*=binpow(len-2,mod-2);
        res%=mod;
        return res;
    };

AC代码

AC

https://codeforces.com/contest/2203/submission/364812724

心路历程（WA，TLE，MLE……）

虽然是权值线段树（树状数组），但是还是加的这个值。

image

不要搞反顺序了。

image

Posted on Edited on

题目大意

题目描述
给定两个整数 ss 和 mm。
你需要构造一个由非负整数组成的数组 a=[a1,a2,…,an]a=[a_1, a_2, \dots, a_n]，满足以下两个条件：

  1. 数组所有元素的和等于 ss，即 ∑i=1nai=s\sum_{i=1}^n a_i = s；

  2. 对于数组中的每一个元素 aia_i，都满足 ai & m=aia_i \ \& \ m = a_i（其中 &\& 表示按位与运算符）。换句话说，在每个数字 aia_i 的二进制表示中，只有当 mm 在相应位置上的二进制位也是 11 时，aia_i 在该位置上的二进制位才可以是 11。

判断是否至少存在一个满足条件的数组。如果存在，求出该数组的最小可能长度 nn；如果不存在，则输出 −1-1。

输入格式
第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例的数量。
每个测试用例包含一行，包含两个整数 ss 和 mm（1≤s,m≤10181 \le s, m \le 10^{18}）。

输出格式
对于每个测试用例，输出一个整数：
如果不存在这样的数组，输出 −1-1；
否则，输出满足条件的数组的最小可能长度 nn。

样例输入

1
2
3
4
5
6
7
6
13 5
13 3
13 6
1000000007 2776648
99999999999 1
998244353 1557287

样例输出

1
2
3
4
5
6
3
5
-1
-1
99999999999
642

样例解释
对于部分测试用例的分析如下：
当 s=13,m=5s=13, m=5 时，答案为 33，因为存在一个满足条件的数组 a=[5,4,4]a=[5, 4, 4]；
当 s=13,m=3s=13, m=3 时，答案为 55，因为存在一个满足条件的数组 a=[3,3,3,3,1]a=[3, 3, 3, 3, 1]；
当 s=13,m=6s=13, m=6 时，答案为 −1-1，因为不存在满足条件的数组。

思路讲解

说白了就是从高位到低位贪心，因为高位你也没办法减的更多了，高位只能影响更高位，而更高位之前已经尽力解决了。因此没有后效性。

1
2
3
4
5
6
7
8
9
10
11
12
13
auto check=[&](ll num_a) -> bool {
    ll opS=S;
    for (ll i=62;i>=0;--i) {
        if ((M>>i)&1) {
            ll cnt=opS/(1ll<<i);
            opS-=min(cnt,num_a)*(1ll<<i);
        }
    }
    if (opS==0) {
        return true;
    }
    return false;
};

AC代码

AC
https://codeforces.com/contest/2203/submission/364386484

心路历程（WA，TLE，MLE……）

Posted on Edited on

基本情况

image

两道题目，哎，还好这个B做的快是吧，绷不住了。

当然了，小号其实也无所谓。嗯，其实也还好不过之后呢，我觉得还是把这个号打上去以后，还是用这个号打。其实，你一直没分数，其实也没什么意思，就是那种比较刺激的那种感觉是吧。

OK，我们说回来。这个D为什么交了5发还是没过呢？主要是因为就是这个D，它的数据量比较大。使用Victor victor或者victor的这种调和级数写法呢，它这个时间会超。可以使用vis 数组标记所有 a 的倍数。这样子可以避免卡常。

1
2
3
4
5
6
7
8
9
10
ll cnt_un_divide=0,cnt_all_divide=0;
vector<char> vis(N+M+2);
for (auto a:A) {
    for (ll i=1;i<=N+M;++i) {
        if (i*a>N+M) {
            break;
        }
        vis[i*a]=true;
    }
}

然后为什么标题里面提了不要用 while 循环？是因为涉及累加的逻辑（在 D 的对拍暴力程序当中），直接 continue 以后，while 循环的这个累加就崩掉了。

A 就是一个向上取整除法，没什么好说的。

B 也简单，就是猜一下，我猜，只有这个 digit 总和小于 10 的情况下，题设条件才成立。注意前导 0，不要不小心进行操作后出现前导 0。

可以在排序前，对第一个数减 1，让其被操作后至少保留 1。

1
2
sn[0]--;
sort(all(sn),greater<>());

心得感悟