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

BDH

B. Mask Allocation

题意

题目读了半天才读懂....

有n*m个口罩，把他们装到盒子里，然后必须满足既可以把这些口罩分成n组，一组m个；也可以将它们分成m组，一组n个。要求分的组数最少，并且字典序最大。

题解

比赛的时候没敢写，没造出来样例，怕演了队友...

就是类似于gcd一样的dfs，如果 n<m 的话，交换n和m，每次取n/m*m个m，然后剩下的n%m个m就继续往下递归，直到口罩分配完。这样写代码有点不美观，可以直接变成类似于辗转相除法一样的。具体看代码。

代码

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

priority_queue<int>ans;

void dfs(int n,int m)
{
    if(n==0||m==0) return;
    if(n<m) swap(n,m);
    for(int i=0;i<m;i++) ans.push(m);
    dfs(m,n-m);
}

int main()
{
    int n,m;
    int t;
    cin>>t;
    while(t--){
    cin>>n>>m;
    dfs(n,m);
    cout<<ans.size()<<endl;
    while(!ans.empty()){
        cout<<ans.top()<<' ';
        ans.pop();
    }
    cout<<endl;
    }
    return 0;
}

D. Fake News

题意

给定一个n，判断 $\sum_{k=1}^{n}k^2$ 是不是一个完全平方数，是的话输出"Fake news!"，否则输出“Nobody knows it better than me!”。

题解

当时的做法是打表，然后大胆猜测只有1和24的时候是Fake news，交一发发现是对的。emmm，具体证明看：https://www.zhihu.com/question/363661682

代码

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

int main()
{
    int T;
    scanf("%d",&T);
    while(T -- )
    {
        ll n;
        scanf("%lld",&n);
        if(n == 1 || n == 24)
            printf("Fake news!\n");
        else
            printf("Nobody knows it better than me!\n");
    }
    return 0;
}

H. Dividing

题意

正整数二元组传奇元组 (n, k) 是这样定义的

• (1, k) 总是传奇元组

• 若 (n, k) 是传奇元组, 那么 (n + k, k) 也是

• 若 (n, k) 是传奇元组, 那么 (nk, k) 也是

• 统计有多少个传奇元组 (n, k) 满足 1 ≤ n ≤ N, 1 ≤ k ≤ K, 其中 N 和 K 是不超过 10¹² 的整数

题解

队友巨巨场上推出了一个公式：N + ( N / 2 + ……+ N /K ) *2 + N%2!=0 + ……+ N%K!=0。造了几个样例发现这个式子是对的，然后数论选手开始工作.gif 。

思路是当k是1的时候，有N个是可行解；当k不是1的时候，那么必须要n%k==0或者(n-1)%k==0，在N内以k为循环的每个循环中会有两个可行解，第一个解%k==1，第二个解%k==0，所以当N%k!=0的时候，n/k个循环外还会有一个第一个解，所以解的个数要加一个。

出题人的题解想法：如果（n，k）是传奇元组，那么一定有下面三个条件中的一个

n==1
n%k==0
(n-1)%k==0

做法

• 先讨论 n%k==0 的情况, 不妨设 n=xk, 那么, x 和 k 中总有一个数字不超过 10⁶ , 枚举 x 和 k 中较小的一个即可, 另一个的个数可以直接通过计算获取

• 对于 (n-1)%k==0 的情况也是同样的

• 对于 n=1 的情况, 直接统计即可

代码

按照队友巨巨公式的代码

#include <cmath>
#include <vector>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
vector<ll> v;
int main() {
    ll n, k;
    scanf("%lld%lld", &n, &k);
    ll ans = n;
    for (ll l = 2, r; l <= k; l = r + 1) {
        if (n/l == 0)break;
        r = min(n/(n/l), k);
        ans = (ans + ((r-l+1) * (n / l)) * 2LL % mod) % mod;
    }
    ll kk = sqrt(n);
    for (ll i = 1; i <= kk; ++i) {
        if (n % i == 0) {
            v.push_back(i);
            if (i == (n/i));
            else {
                v.push_back(n/i);
            }
        }
    }
    ans = (ans + k) % mod;
    for (int i = 0; i < (int)v.size(); ++i) {
        if (k >= v[i]) ans--;
    }
    ans = (ans % mod + mod) % mod;
    printf("%lld\n", ans % mod);
    return 0;
}

按照出题人思路的代码

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const ll mod=1e9+7;

int main()
{
    ll n,k;
    cin>>n>>k;
    ll ans=(n+k-1)%mod;
    for(ll i=2;i<=min(n,k);i++){
        ll j=min(n/(n/i),k);
        ans=(ans+(j-i+1)%mod*(n/i)%mod)%mod;
        i=j;
    }
    n--;
    for(ll i=2;i<=min(n,k);i++){
        ll j=min(n/(n/i),k);
        ans=(ans+(j-i+1)%mod*(n/i)%mod)%mod;
        i=j;
    }
    cout<<ans<<endl;
    return 0;
}