牛客多校Day_7

2020-08-02

这里是牛客多校Day7的补题

赛场回顾

一共就过了BD两题……第三个签到题H都没过，丢人.jpg

D

题意

对于$N = \sum_{k=1}^{n}k^2$，请验证$N$是否为square number即完全平方数。

做法

看到样例觉得只有$n=1$时$N$才有可能是完全平方数，果断白给一发……

首先对于这个问题是有结论的：当且仅当 $n=1$或$n=24$时$N$才为完全平方数。

不严谨的瞎猜：我们首先知道对于公式

$N = \sum_{k=1}^{n}k^2 = \frac{n \times (n+1) \times (2 \times n + 1)}{ 6 }$

这里可以看到在$n=24$时，对应有$\frac{ 24 }{ 6 }$,$24+1$以及$2 \times 24 + 1$三个完全平方数，当n继续变大时难以找到下一个……..

严谨的证明：

这不是一个简单的问题，它在数学上小有名气，称为Cannonball problem。1918年被一个叫G.N.Watson 的人用椭圆函数解决，1990年才发现一个初等证明。

Link

代码

void solve(){
    ll n=read();
    if(n==1||n==24){
        puts("Fake news!");
    }
    else {
        puts("Nobody knows it better than me!");
    }
    return ;
}

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$的子问题，不断循环即可。

代码

//wrfNB!!!
#include<bits/stdc++.h>
using namespace std;
 
vector<int> func(int n,int m){
    if(n>m)return func(m,n);
     
    vector<int>res;
    if(n==0)return res;
    if(n==1){
        for(int i=0;i<m;i++){
            res.push_back(n);
        }
        return res;
    }
    int k=m/n,b=m-k*n;
    for(int i=0;i<n*k;i++){
        res.push_back(n);
    }
    vector<int>tmp=func(n,b);
    for(int item:tmp){
        res.push_back(item);
    }
    return res;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        auto ans=func(n,m);
        printf("%d\n",ans.size());
        for(int item:ans)printf("%d ",item);
        printf("\n");
    }
    return 0;
}

赛后补题

正整数二元组 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}$ 的整数