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

D. Fake News $\looparrowright$

题目描述

McDonald Thumb, the greatest president ever in the history of the Great Tokitsukaze Kingdom has held his 100th press conference about the global pandemic after making his 1000000th tweets with his smartphone. With a big smile on his face, Mr. Thumb said that nobody knows math more than he does.
“I learn math since I was born and I am very good at it,”, said Mr. Thumb," People keep asking me why I know math so much and I sometimes find myself having those amazing ideas about math."
“For example?”, asked by a reporter.
“Oh you, I know you! Fake news! You and your agency always produce fake news!”, replied angrily by Mr. Thumb," Let me teach you something, do you know if you add up the squares of numbers from $1$ to $n$ , the sum will never be a square number?"
As another reporter in that press conference, you also wondering that given $n$ , whether $\sum\limits_{k=1}^{n}k^2$ is a square number. Specifically, we regard a positive number $x$ as a square number when there exists an integer $y$ satisfying $y^2=x$ .

输入描述

There are multiple test cases. The first line of the input contains an integer $T\ (1 \leqslant T \leqslant 10^6)$ indicating the number of test cases.
For each test case, the first line contains one integers $n\ (1 \leqslant n \leqslant 10^{15})$ .

输出描述

If the sum is a square number, please output “Fake news!” in one line. Otherwise, please output “Nobody knows it better than me!” instead.

示例1

输入

输出

Fake news!
Nobody knows it better than me!
Nobody knows it better than me!
Nobody knows it better than me!
Nobody knows it better than me!

分析

打表题，当且仅当 $n=1$ 或 $n=24$ 时， $\sum\limits_{k=1}^nk^2$ 为完全平方数。
知乎上的巨佬们给出了一些证明。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第七场）Problem D
Date: 8/27/2020
Description: Just Attempt
*******************************************************************/
#include<stdio.h>
int main(){
	int _;
	for(scanf("%d",&_);_;_--){
		long long n;
		scanf("%lld",&n);
		if(n==1||n==24){
			puts("Fake news!");
		}else{
			puts("Nobody knows it better than me!");
		}
	}
	return 0;
}

H. Dividing $\looparrowright$

题目描述

The following rules define a kind of integer tuple - the Legend Tuple:
$(1, k)$ is always a Legend Tuple, where k is an integer.
if $(n, k)$ is a Legend Tuple, $(n + k, k)$ is also a Legend Tuple.
if $(n, k)$ is a Legend Tuple, $(nk, k)$ is also a Legend Tuple.
We want to know the number of the Legend Tuples $(n, k)$ where $1 \leqslant n \leqslant N$ , $1 \leqslant k \leqslant K$ .
In order to avoid calculations of huge integers, report the answer modulo $10^9+7$ instead.

输入描述

The input contains two integers $N$ and $K$ , $1 \leqslant N, K \leqslant 10^{12}$ .

输出描述

Output the answer modulo $10^9+7$ .

示例1

输入

3 3

输出

示例2

输入

3 9

输出

分析

所有 Legend Tuple 从 $(1,k)$ 出发，会产生 $(xk,k)$ 和 $(xk+1,k)$ 两种情况（ $x\in\mathbb N^\ast$ ）；其中， $(xk+1,k)$ 的情况经过一步操作可以变成 $(xk,k)$ 的情况。
显然，当且仅当 $k\mid (n-1)$ 或 $k\mid n$ 时， $(n,k)$ 为 Legend Tuple。
对于 $k\mid(n-1)$ 的情况，其贡献为 $\sum\limits_{k=1}^K\sum\limits_{n=1}^N\left[k\mid(n-1)\right]=\sum\limits_{k=1}^K\left\lfloor\frac{N-1}{k}\right\rfloor+K$ ； $\sum\limits_{k=1}^K\left\lfloor\frac{N-1}{k}\right\rfloor$ 为 $n\geqslant 2$ 的贡献， $K$ 为 $n=1$ 的贡献。
对于 $k\mid n$ 的情况，其贡献为 $\sum\limits_{k=1}^K\sum\limits_{n=1}^N [k\mid n]=\sum\limits_{k=1}^K\left\lfloor\frac{N}{k}\right\rfloor$ 。
对于两部分贡献，有 $(1,1),(2,1),\cdots,(N,1)$ 这部分的贡献是重复的，需要减去重复的一份贡献 $N$ 。
因此最终的答案为 $\sum\limits_{k=1}^K\sum\limits_{n=1}^N [k\mid n]=\sum\limits_{k=1}^K\left\lfloor\frac{N}{k}\right\rfloor+\sum\limits_{k=1}^K\sum\limits_{n=1}^N\left[k\mid(n-1)\right]=\sum\limits_{k=1}^K\left\lfloor\frac{N-1}{k}\right\rfloor+K-N$ 。可以用数论分块解决。
当然， $N=1$ 或 $K=1$ 时需要进行特判：当 $N=1$ ，答案为 $K$ ；当 $K=1$ ，答案为 $N$ 。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第七场）Problem H
Date: 8/28/2020
Description: Block
*******************************************************************/
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll N,K;
ll cal(ll n,ll k){
	//数论分块
	ll l,r;
	ll ans=0;
	for(l=1;l<=k;l=r+1){
		if(n/l==0){
			break;
		}
		r=min(k,n/(n/l));
		ans+=(r-l+1)*(n/l)%mod;
		ans%=mod;
	}
	return ans;
}
int main(){
	cin>>N>>K;
	if(N==1){
		cout<<K%mod<<endl;
	}else if(K==1){
		cout<<N%mod<<endl;
	}else{
		cout<<((cal(N,K)+cal(N-1,K)+K-N)%mod+mod)%mod<<endl;
	}
	return 0;
}