2020牛客暑期多校训练营（第七场）解题报告

D

温暖的签到题。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

int main(){
	int T=input();
	while(T--){
		ll n=input();

		if(n==1||n==24){
			printf("Fake news!
");
		}else{
			printf("Nobody knows it better than me!
");
		}
	}
}

B

数学题？我们设(n<m)，当医院数量为(n)时候需要给每个医院安排(m)个口罩，那么我们可以分别给每个医院安排(lfloor frac{n}{m} floor)个装了(n)个口罩的盒子，此时每个医院还要额外再拿(m mod n)个口罩才能达到要求。当医院的数量为m时，也用相似的思路解决就行了。然后(gcd)搞一搞就可以了。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

#define PII pair <int,int>
#define fr first
#define sc second
#define mp make_pair

int cnt=0;
vector<PII> Ans;

void gcd(int n,int m,int sum){
	if(n<m) swap(n,m);
	if(m==0){
		cnt+=(sum/n);
		Ans.push_back(mp(n,sum/n));
		return;
	}
	int tmp=n/m;
	Ans.push_back(mp(m,m*tmp));
	sum-=m*m*tmp;
	cnt+=tmp*m;
	if(sum) gcd(m,n%m,sum);
}

int main(){
	int T=input();
	while(T--){
		int n=input(),m=input();
		cnt=0;
		Ans.clear();
		gcd(n,m,n*m);
		printf("%d
",cnt);
        for(int i=0;i<Ans.size();i++){
            for(int j=0;j<Ans[i].second;j++){
                printf("%d ",Ans[i].first);
            }
        }
        printf("
");
	}
}

H

数学题。易推出答案的公式为：((sum_2^kfrac{n}{k}+frac{n-1}{k})+k-1)。用整除分块随便搞搞就行了。复杂度(O(sqrt n))

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

const ll mod=1e9+7;

ll cal(ll n,ll k){
	ll res=0;
	for(int i=2,j;i<=n&&i<=k;i=j+1){
		if(n/i!=0) j=min(n/(n/i),k);
        else j=k;
        res=(res+n/i*(j-i+1))%mod;
    }
    return res;
}

int main(){
	ll n=input(),k=input();

	printf("%lld
",((cal(n,k)+cal(n-1,k))%mod+n+k-1)%mod);
}