B、Mask Allocation

$题意：T组输入T\leq100，每组输入给出n，m\leq10^4$
$要我们找到一些数既可以组合成n个m，也可以组合成m个n，并且需要输出字典序最大的那个组合$
$Solution：首先我们假设n<m，那么显然的结论是我们每一个盒子都不能超过n$
$一旦超过了n，要组成m个n就永远不可能办到，第二个要求是字典序最大$
$那么我们就把n个大小为n的口罩放在最前面就可以保证字典序一定是当前最大的$
$如果我们要满足n个医院每个m个口罩，那么我们每个医院还要剩下m-n个缺口需要补上$
$如果我们要满足m个医院每个n个口罩，显然前面已经满足过n个医院了，还剩下m-n个医院要满足n个口罩$
$这里你就会发现开始套娃了，之前是要用n和m，现在是m-n满足n。即可发现递归规律$
$发现我们每次都只需要取k=min(m-n,n)里面循环k次k，直到一方满足了需求，程序就结束了$

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define mk(__x__,__y__) make_pair(__x__,__y__)
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

const int N = 1e5 + 7;
vector<int> a;

int main() {
    int T = read();
    while (T--) {
        a.clear();
        int n = read(), m = read();
        while (n) {
            if (n < m)    swap(n, m);
            for (int i = 1; i <= m; ++i)    a.push_back(m);
            n -= m;
        }
        print(a.size());
        for (auto it : a)
            print(it, 32);
        puts("");
    }
    return 0;
}

D、Fake News

$给出k\leq10^{15},询问从1到k的全部数平方相加是不是一个完全平方数，打表题，我是打表过的$
$具体证明不太懂，可以百度具体证明方法，最后只有1和24是完全平方数，也可以开始写个暴力直接打表$
$等计算机跑一会就行了$

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define mk(__x__,__y__) make_pair(__x__,__y__)
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)  putchar(op); return; }  char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

const int N = 1e5 + 7;

int main() {
    int T = read();
    while (T--) {
        ll n = read();
        if (n == 1 or n == 24)  puts("Fake news!");
        else puts("Nobody knows it better than me!");
    }
    return 0;
}

H、Dividing

$题目意思：给出N，K\leq10^{12}元组（n，k）是满足范围要求中的全部元组$
$首先给出(1,k)一定是一个满足条件的元组，而且如果(n,k)是一个元组那么(n+k,k)和(nk,k)也是元组$
$现在要我们求其中数据范围内有多少组满足条件的元组$
$我们发现(1,k)可以那么(k,k),(k+1,k),(2*k,k),(2*k+1,k)也一定可以并且这就是全部的可能$
$那么我们方向思维，如果要从1递推到可以的元组，也就是元组中的n可以通过/k或者-k的方式变成1$
$再观察上面写出的式子，看出一定n是k的倍数或者n-1是k的倍数的前提下就可以满足题目条件的元组$
$再通过整数分块可以求到再min(n,k)中的从2倍开始(i,j)对数量即i=2*j或者3*j累计下去的数量$
$求一遍n下再求一遍n-1下，如何满足答案绝对不重复呢，再大于k直接break就行了k*(k+1)=k*k+K,这里可以直接跳出就行了$
$再判断n=1的情况下可以取到全部的k，取1，可以取到全部的n，(1,1)算了2边减掉1即可，答案就可以算到了$

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define mk(__x__,__y__) make_pair(__x__,__y__)
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

ll n, k, ans;

ll find(ll x) {
    ll res = 0;
    for (ll i = 2, j; i <= x and i <= k; i = j + 1) {
        j = min(x / (x / i), k);
        (res += (j - i + 1) % MOD * (x / i) % MOD) %= MOD;
    }
    return res;
}

int main() {
    n = read(), k = read();
    ans = find(n) + find(n - 1);
    print((ans + n + k - 1) % MOD);
    return 0;
}

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

B、Mask Allocation

D、Fake News

H、Dividing