2020牛客暑期多校训练营第七场

发表于 分类于 ， ， 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

比赛链接

https://ac.nowcoder.com/acm/contest/16151?&headNav=www

D. Fake News

题意

输入一个数\(n\)，问你\(\begin{aligned}\sum_{i=1}^n i^2\end{aligned}\) 是不是一个完全平方数。

数据范围

\(10^6\)组输入

\(n\lt 10^{15}\)

题解

前缀和为\(\frac{n\cdot(n+1)\cdot(2n+1)}{6}\), 由于\(n\)，\(n+1\)，\(2n+1\)两两互质，所以他们排除掉\(2\)和\(3\)这两个因子以后是完全平方数。直接验证这个就可以了。

H. Dividing

题意

  • (1,k)合法
  • 如果(n,k)合法，则(n+k,k)合法
  • 如果(n,k)合法，则(nk,k)合法

输入\(N\),\(K\), 问你有多少组\(1\le n\le N,1\le k\le K\)合法。

题解

显然每个\(k\)都是独立的。

考虑n的k进制，很容易发现第一句话说的是\(1\)合法，第二句话说的是合法的数加上\(10\)合法，第三句话说的是合法的数左移一位合法。

所以很容易发现，只要最低位为0或者1，就是合法的。

然后就是一个分块的模版题了。计算\(\begin{aligned}\sum_{i=1}^K \sum_{j=1}^N [j\mod i\le 1]\end{aligned}\)

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
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int mod = 1e9 + 7;

// [0,n] sum n/i
ll cal(ll k, ll n) {
    ll ans = 0, pos;
    // i=1, min(n,k)
    for (ll i = 1; i <= min(n, k); i = pos + 1) {
        pos = n / (n / i);
        pos = min(pos, min(n , k));
        //doing something
        ans += (pos - (i - 1)) * (n / i);
        ans %= mod;
    }
    // i=min(n,k)+1 , k
    return ans;
}

ll cal2(ll k, ll n) {
    if(k == 1) {
        return 0;
    }
    ll ans = 0, pos;

    for (ll i = 2; i <= min(n - 1, k); i = pos + 1) {
        pos = (n - 1) / ((n - 1) / i);
        pos = min(pos, min(n - 1, k));
        //doing something
        ans += (pos - (i - 1)) * ((n - 1) / i);
        ans %= mod;
    }
    ans += k-1;
    return ans % mod;
}

int main() {
    ll n, k;
    scanf("%lld %lld", &n, &k);
   // cout << cal(k, n) << " " << cal2(k, n) << endl;
    ll ans = (cal(k, n) + cal2(k, n));
    printf("%lld", ans % mod);
}


B. Mask Allocation

题意

给你\(n\times m\)个口罩，你可以对口罩进行分组，要求分组后可以在不拆开组的情况下，分配给n个医院。每个医院m个口罩，也可以分配给m个医院，每个医院n个口罩。

数据范围

\(100\)组输入

\(1\le n,m \le 10^4\)

题解

不妨考虑\(n<m\), 那么我们直接分出n个n，那么后面剩余\(n\times m-n\times n\)个口罩，要求可以分成\(m-n\)个n，以及n个\(m-n\)，注意到出现了子问题。所以递归解决。