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

比赛链接

A

B Mask Allocation

不妨设 $n<m$，我们先把 $m$ 个 $n$ 放好，然后发现，前 $\left\lfloor\frac{m}{n}\right\rfloor\times n$ 个数字不需要动了，它们能形成 $n$ 个 $\left\lfloor\frac{m}{n}\right\rfloor$；还剩下 $m\bmod n$ 个 $n$，要把他们分成 $n$ 个 $m\bmod n$，这就是子问题了，递归就好。复杂度等同于欧几里得算法。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

vi solve(int n, int m){
	if(n > m)	swap(n, m);
	if(n == 0)	return vi();
	vi res;
	for(int i = 1; i <= m / n; i++)
		for(int j = 1; j <= n; j++)
			res.pb(n);
	vi tmp = solve(n, m % n);
	if(res.size() < tmp.size())	swap(res, tmp);
	for(auto &k : tmp)	res.pb(k);
	return res;
}

int main(){
	int T, n, m;
	for(read(T); T; T--){
		read(n, m);
		vi ans = solve(n, m);
		sort(ans.begin(), ans.end());
		reverse(ans.begin(), ans.end());
		printf("%d\n", (int)ans.size());
		for(auto &k : ans)	printf("%d ", k);
		puts("");
	}
	return 0;
}

---

D Fake News

有个结论，$\sum\limits_{k=1}^nk^2$ 是一个完全平方数 $\iff$ $n=1$ 或 $n=24$.

不过我们怎么可能知道这个结论呢…… 我们是这样做的：$\sum\limits_{k=1}^nk^2=\frac{n(n+1)(2n+1)}{6}$，注意到 $n,n+1,2n+1$ 两两互质，所以要使原式是完全平方数，就必须在除掉 $6$ 之后，三个数本身就是完全平方数。

证明：$n,n+1,2n+1$ 两两互质。

证：$n,n+1$ 互质是大家都知道的；设 $\gcd(n,2n+1)=g$，$n=ag,\;2n+1=bg$，那么 $(b-2a)g=1$，只能是 $g=1$；设 $\gcd(n+1,2n+1)=g$，$n+1=ag,\;2n+1=bg$，那么 $(2a-b)g=1$，只能是 $g=1$。证毕。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T;
LL n;

int main(){
	for(read(T); T; T--){
		read(n);
		LL a = n, b = n + 1, c = 2 * n + 1;
		if(a % 2 == 0)	a /= 2;
		else	b /= 2;
		if(a % 3 == 0)	a /= 3;
		else if(b % 3 == 0)	b /= 3;
		else	c /= 3;
		LL sqa = sqrt(a), sqb = sqrt(b), sqc = sqrt(c);
		if(sqa * sqa == a && sqb * sqb == b && sqc * sqc == c)
			puts("Fake news!");
		else	puts("Nobody knows it better than me!");
	}
	return 0;
}

---

H Dividing

只要一个数是 $k$ 的倍数或者 $\bmod k$ 余 $1$，那么它就会被统计。

所以我们要算的就是：$\sum\limits_{k=1}^K\sum\limits_{i=1}^N[k\mid i\;或\;k\mid i-1]$.

推一下：

$$\begin{align} \sum_{k=1}^K\sum_{i=1}^N[k\mid i\;或\;k\mid i-1]&=\sum_{k=2}^K\sum_{i=1}^N[k\mid i]+\sum_{k=2}^K\sum_{i=1}^N[k\mid i-1]+N&&注意\;k=1\;有重复，所以单独拿出来计算\\ &=\sum_{k=2}^K\sum_{i=1}^N[k\mid i]+\sum_{k=2}^K\sum_{i=1}^{N-1}[k\mid i]+N+K-1&&i=0\;也单独统计\\ &=\sum_{k=2}^K\left\lfloor\frac{N}{k}\right\rfloor+\sum_{k=2}^K\left\lfloor\frac{N-1}{k}\right\rfloor+N+K-1 \end{align}$$

这就是数论分块的裸题了。

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const LL MOD = 1e9+7;

int main(){
	LL n, k;
	read(n, k);
	LL ans = 0;
	for(LL l = 2, r; l <= k; l = r + 1){
		if(n / l == 0)	r = k;
		else	r = min(k, n / (n / l));
		(ans += (r - l + 1) * (n / l) % MOD) %= MOD;
	}
	n--;
	for(LL l = 2, r; l <= k; l = r + 1){
		if(n / l == 0)	r = k;
		else	r = min(k, n / (n / l));
		(ans += (r - l + 1) * (n / l) % MOD) %= MOD;
	}
	(ans += n + k) %= MOD;
	printf("%lld\n", ans);
	return 0;
}