这里是牛客多校Day7的补题
赛场回顾
一共就过了BD两题……第三个签到题H都没过,丢人.jpg
D
题意
对于$N = \sum_{k=1}^{n}k^2$,请验证$N$是否为square number即完全平方数。
做法
看到样例觉得只有$n=1$时$N$才有可能是完全平方数,果断白给一发……
首先对于这个问题是有结论的:当且仅当 $n=1$或$n=24$时$N$才为完全平方数。
不严谨的瞎猜:我们首先知道对于公式
这里可以看到在$n=24$时,对应有$\frac{ 24 }{ 6 }$,$24+1$以及$2 \times 24 + 1$三个完全平方数,当n继续变大时难以找到下一个……..
严谨的证明:
这不是一个简单的问题,它在数学上小有名气,称为Cannonball problem。1918年被一个叫G.N.Watson 的人用椭圆函数解决,1990年才发现一个初等证明。
代码
1 | void solve(){ |
B
题意
有$n \times m$个物品,在装箱最少且个数平均的情况下,既能平均分给给$n$个也能平均分给$m$个医院。
做法
此时不妨设 $n<m$ ,由于要求了字典序最大,因此考虑装箱时箱内物品数量尽可能大,但显然不能超过$n$,否则人数在$m$时这些箱子子无法分发
继续考虑字典序最大,在医院数量为$n$时,需要给每个医院安排$m$个物品,因此至多给每个医院安排$\lfloor (\frac{m}{n}) \rfloor$个装有$n$个物品的箱子,这里已经安排了$\lfloor (\frac{m}{n}) \lfloor \times n$个物品,此时还需要每个医院额外再拿 $m \% n$个口罩才能达到要求。
这时候我们考虑医院数量为$m$的情况,此时需要给每个医院分配$n$个口罩,那显然已经有$\lfloor(m/n) \rfloor \times n$个医院满足条件了,还有$m \% n$个医院还啥都没拿到
这样,我们就把问题转化成了$n’= m \% n,m’= n$的子问题,不断循环即可。
代码
1 | //wrfNB!!! |
赛后补题
H
题意
正整数二元组 Legend Tuple (n, k) 是这样定义的
• (1, k) 总是 Legend Tuple
• 若 (n, k) 是 Legend Tuple, 那么 (n + k, k) 也是
• 若 (n, k) 是 Legend Tuple, 那么 (nk, k) 也是
• 统计有多少个 Legend Tuple (n, k) 满足 1 ≤ n ≤ N, 1 ≤ k ≤ K, 其中 N 和 K 是不超过 $10^{12}$ 的整数