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

比赛链接

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$,注意到出现了子问题。所以递归解决。