2020牛客多校第七场BDH题解

D. Fake News

题意

求 $\sum_{n=1}^k n^2$ 的结果是不是平方数。n<1e15

解题思路

根据公式 $\sum_{n=1}^k n^2=\frac{1}{6}n(n+1)(2n+1)$ ，分别判断 $\frac{1}{6}n,n+1,2n+1$ 是否为平方数。注意这里不能算出来，会超时。题解的方法是【三个乘数分别先两两除下gcd，然后分别判定sqrt是否等于自己就好。】
同样根据上述的公式，可以猜出来只有1和24的时候成立，n再大时n+1和2n+1就无法达到平方数较大的差距了。
如何证明 1²+2²+…+n² 为平方数的解只有 n＝1 或 n＝24？

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int t;
ll n;

int is(ll n) {
    ll x = sqrt(n);
    return x*x==n;
}

int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%lld",&n);
        if(is(n/6)&&is(n+1)&&is(2*n+1)||n==1)
        puts("Fake news!");
        else puts("Nobody knows it better than me!");
    }
}

B. Mask Allocation

题意和题解官方文档讲的很清楚了。

题意：n*m个口罩，装最少的箱，使得在个数平均的情况下，既能分箱分给n个医院，也能分给m个医院。

不妨设（n<m）由于要求字典序最大，所以考虑装口罩最多的盒子，显然不能超过n，不然人数在m的时候这盒子分不出去了。
那继续考虑字典序最大，医院数量为n时候需要给每个医院安排m个口罩，我们至多给每个医院安排 floor(m/n)个装了n个口罩的盒子，那这里就安排了floor(m/n)n个盒子，此时每个医院还要额外再拿 m%n个口罩才能达到要求。
这时候我们考虑医院数量为m的情况，此时需要给每个医院分配n个口罩，那显然已经有floor(m/n)n个医院满足条件了，还有m%n个医院还啥都没拿到。
这样，我们就把问题转化成了n’= m % n，m’= n的子问题，不断循环即可。就是gcd

#include <bits/stdc++.h>
using namespace std;
int t,n,m;
vector<int> v;
int gcd(int a, int b) {
    if(b==0) return a;
    for(int i=1;i<=a/b*b;i++) v.push_back(b);
    return gcd(b, a%b);
}
int main() {
    scanf("%d",&t);
    while(t--) {
        v.clear();
        scanf("%d%d",&n,&m);
        gcd(max(n,m),min(n,m));
        printf("%d\n",v.size());
        for(int i=0;i<v.size();i++) {
            printf("%d ",v[i]);
        }
        printf("\n");
    }
}

队友比赛期间写的代码，用的其实是更相减损而不是辗转相除。

int t;
int n,m;
int cnt = 0;
int ans[maxn];
void DFS(int x,int n,int m,int k)
{
    //printf("%d %d\n",m,k);
    ans[++cnt] = m;
    if(k==0) return ;
    n = max(k,m), m = min(k,m);
    DFS(x+1,n,m,n-m);
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        if(n<m) swap(n,m);
        cnt = 0;
        DFS(0,n,m,n-m);
        ans[0] = 1;
        int tot = 0;
        for(int i=1;i<=cnt;++i) tot+=ans[i];  printf("%d\n",tot);
        for(int i=1;i<=cnt;++i)
        {
            int j = ans[i];
            while(j--)
            {
                printf("%d ",ans[i]);
            }
        }

        printf("\n");
    }
    return 0;
}

H. Dividing

题意

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

解题

数论分块。
先说结论：(n, k) 是 Legend Tuple 当且仅当满足下面三个条件的某一个 ① n=1 ② n 是 k 的倍数 ③ n-1 是 k 的倍数。
在k任意取的条件下，n只要满足n%k=0或者n%k=1即可。即求 $\sum_{i=1}^k\lfloor\frac{N}{k}\rfloor+\sum_{i=1}^k\lfloor\frac{N-1}{k}\rfloor$

贴一个队友的代码，没有其他代码那么好懂。

int t;
ll n,k;
int main() {
    scanf("%lld%lld",&n,&k);
    ll ans = 0;
    ll tmp1 = 0, tmp2 = 0;
    for(ll x = 2 , gx; x<=k ; x = gx+1) {
        gx = n/x?min(n/(n/x),k):k;
        tmp1= (tmp1 + (gx-x+1)%mod*(n/x)%mod)%mod;
    }
    --n;
    for(ll x = 2 , gx; x<=k ; x = gx+1) {
        gx = n/x?min(n/(n/x),k):k;
        tmp2= (tmp2 + (gx-x+1)%mod*(n/x)%mod)%mod;
    }
    ++n;
    ans = ((tmp1 + tmp2 + n + k-1)%mod+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}