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

B. Basic Gcd Problem $\looparrowright$

题目描述

As a great ACMer, ZYB is also good at math and number theory.
ZYB constructs a function f_c(x) such that:

$$ f_c(x)=\left\{\begin{matrix} \max\limits_{1\leqslant i\leqslant x-1}cf_c(\gcd(i,x)) &x>1\\ 1&x=1 \end{matrix}\right. $$

Give some positive integer pairs $(n_i, c_i)$, ZYB wants to know $f_{c_i}(n_i)\bmod (10^9+7)$.

输入描述

The input contains multiple test cases. The first line of input contains one integer $T$ $(1 \leqslant T \leqslant 10^6)$.
In the following $T$ lines, each line contains two integers $n_i, c_i$ $(1 \leqslant n_i, c_i \leqslant 10^6)$ describing one question.

输出描述

For each test case, output one integer indicating the answer.

示例1

输入

2  
3 3  
10 5

输出

3  
25 

分析

题目给出了一个可递归求解的函数，递归停止的条件为：当 $x=1$，$f_c(x)=1$。递推式为 $f_c(x)=\max\limits_{1\leqslant i\leqslant x-1} cf_c(\gcd(i,x))$，$c$ 可以看作常数，若递归了 $n$ 次，那么就会产生乘子 $c^n$。由于每次递归都取 $\max$，所以递归的次数要尽量多（也就是让乘子尽量大）。最多可以递归 显然，若 $f_c(x)$ 最多可以递归 $n$ 次，则 $f_c(x)=c^n$，我们要求的就是最大的递归次数。
递归次数显然与 $\gcd(i,x)$ 有关。由算数基本定理，当 $x>1$，可以将 $x$ 写成多个质数的乘积，不妨设 $x=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$，质因子个数为 $cnt_x=\sum\limits_{i=1}^m k_i$。经过一次递归，就会求一次 $\gcd$，就会损失一定数量的质因子。如果每次递归只损失一个质因子，那么递归次数显然是最多的，为 $cnt_x$；这样的方案是存在的，比如说 $i=p_1^{k_1-1}p_2^{k_2}\cdots p_m^{k_m}$。
综上所述，$f_c(x)=c^{cnt_x}$，$cnt_x$ 为 $x$ 的质因子数量。
若每组测试数据单独求质因子数量，时间复杂度为 $O(T\sqrt n)$，会 $\text{TLE}$。不妨直接用欧拉筛在线性时间内得到 $1\sim 10^6$ 内各个整数的质因子数量。若 $x$ 为质数，那么 $cnt_x=1$；若 $x$ 为合数，有递推式 $cnt_{x\times p}=cnt_x+1$，其中 $p$ 为质数。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第四场） Problem B
Date: 8/15/2020
Description: Euler Sieve And GCD
*******************************************************************/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=1000006;
const int mod=1000000007;
int _;
bool isprime[N];
ll prime[N>>1];
ll cnt[N];
void EulerSieve(int);
ll qpow_mod(ll,int);
int main(){
	EulerSieve(1000000);
	for(cin>>_;_;_--){
		int n,c;
		scanf("%d%d",&n,&c);
		printf("%lld\n",qpow_mod(c,cnt[n]));
	}
	return 0;
}
void EulerSieve(int maximum){
	memset(isprime,true,sizeof(isprime));
	int num=0;
	ll i,j;
	for(i=2;i<=maximum;i++){
		if(isprime[i]){
			prime[++num]=i;
			cnt[i]=1;
		}
		for(j=1;j<=num&&i*prime[j]<=maximum;j++){
			isprime[i*prime[j]]=false;
			cnt[i*prime[j]]=cnt[i]+1;
			if(i%prime[j]==0){
				break;
			}
		}
	}
}
ll qpow_mod(ll a,int b){
	ll res=1;
	while(b){
		if(b&1){
			res=res*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

F. Finding the Order $\looparrowright$

题目描述

ZYB has a so-called smart brain. He can always point out the key-point in a complex problem.
There are two parallel lines $AB$ and $CD$ in a plane. $A,B,C,D$ are all distinct points.
You only know the Euclidean Distances between $AC,AD,BC,BD$. But you don’t know the exact order of points (i.e. You don’t know whether it’s $AB$ $// CD$ or $AB// DC$).
Could you determine the order of points quickly, like the ZYB does?

输入描述

The input contains multiple cases. The first line of the input contains a single integer $T$ $(1 \leqslant T \leqslant 100)$, the number of cases.
For each case, there are four integers $a,b,c,d$ $(1 \leqslant a,b,c,d \leqslant 1000)$ in a line, indicating the distances between $AC,AD,BC,BD$.
It is guaranteed that each case corresponds to a valid solution.

输出描述

For each case, output AB//CD (Quotation marks) if $AB//CD$, or output AB//DC (Quotation marks) if $AB //DC$.

示例1

输入

2  
3 5 5 3
5 3 3 5
````
#### 输出    

AB//CD
AB//DC

### 分析    
由三角形三边关系，$p+s>x$，$r+q>y$，故 $p+q+r+s>x+y$。  
![3.png](https://i.loli.net/2020/08/15/1Bdk5oW8tD93REF.png)  
当 $AB//CD$，有 $AD+BC>AC+BD$。  
![1.png](https://i.loli.net/2020/08/15/ixRHMmTcG3eC2PB.png)  
当 $AB//DC$，有 $AC+BD>AD+BC$。  
![2.png](https://i.loli.net/2020/08/15/Qs6y8oxbKNetzvu.png)  
找到了完全相反的两个结论，可以作为判断的依据。  

### 代码  
```cpp
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第四场） Problem F
Date: 8/15/2020
Description: Computational Geometry
*******************************************************************/
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int _;
	for(cin>>_;_;_--){
		int AC,AD,BC,BD;
		scanf("%d%d%d%d",&AC,&AD,&BC,&BD);
		puts(AD+BC>AC+BD?"AB//CD":"AB//DC");
	}
	return 0;
}

H. Harder Gcd Problem $\looparrowright$

题目描述

After solving the Basic Gcd Problem, ZYB gives you a more difficult one:
Given an integer $n$, find two subset $\mathbb A$ and $\mathbb B$ of $\{1,2,\dots,n\}$ such that: ${|\mathbb A|=|\mathbb B|=m}$ and $\mathbb A \cap \mathbb B = \emptyset$; let $\mathbb A=\{a_1,a_2,\cdots,a_{m}\}$ and $\mathbb B=\{b_1,b_2,\cdots,b_m\}$, there exists two permutations $p_1,p_2,\cdots,p_m$ and $q_1,q_2,\cdots,q_m$ such that for each $1 \leqslant i \leqslant m$, $\gcd(a_{p_i}, b_{q_i}) > 1$.
Please find two subsets with maximum value of $m$.

输入描述

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases.
For each test case, there is only one line containing an integer $n$ $(4 \leqslant n \leqslant 2 \times 10^5)$. It’s guaranteed that the sum of $n$ of all test cases will not exceed $2 \times 10^5$.

输出描述

For each test case, output an integer $m$ in the first line. In the next $m$ lines, each contains two integers $a_i$ and $b_i$ $(\gcd(a_i, b_i) > 1)$, denoting the $i$-th element in subset $\mathbb A$ and $\mathbb B$.
If there are multiple solutions, you can output any of them.

示例1

输入

2
4
10

输出

1
2 4
4
3 9
5 10
8 2
4 6

分析

题意描述较为复杂，不妨直接令 $p$ 和 $q$ 都为 $1\sim n$ 的标准排列，那么问题转化为：在区间 $[1,n]$ 中取出尽量多的正整数对 $(x,y)$，满足 $\gcd(x,y)>1$，且每个数字只能使用一次；将 $x$ 放入序列 $a$，$y$ 放入序列 $b$，序列的长度为 $m$，$\forall i\in[1,m]$，且 $i\in\mathbb N^\ast$，有 $\gcd(a_i,b_i)>1$。
显然，对于 $1\sim n$ 之间的全体偶数，可以随意配对。所以我们暂且不考虑偶数，将偶数放到最后配对。
先枚举除 $2$ 以外所有不超过 $n$ 的质数 $p$，对于 $2p>n$ 的质数 $p$，不存在与其配对的数，首先将其剔除。若质数 $2p\leqslant n$，那么对于不大于 $n$ 的 $p$ 的倍数，可以组成集合 $\mathbb P=\{x=kp|x\leqslant n,k\in\mathbb N^\ast\}$；显然，若集合 $\mathbb P$ 中任意两个元素都不互质；若 $\mathrm{card}(\mathbb P)$ 为偶数，那么正好可以两两配对；若 $\mathrm{card}\left(\mathbb P\right)$ 为奇数，取出 $\mathbb P$ 中一个偶数暂时不用（事实上，$\mathbb P$ 中一定会包含 $2p$），将剩余元素两两配对。此时，一部分偶数已经配对，如 $2p,4p,\cdots$。
最后，将剩下的还没配对的偶数两两配对。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第四场） Problem H
Date: 8/18/2020
Description: Number Theory, Construction
*******************************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=200009;
int _;
int prime[N>>1];//质数
bool notprime[N];
int tot;
bool used[N];//记录是否使用
vector<int>ans;//记录答案
void EulerSieve(int);//欧拉筛
int main(){
	EulerSieve(N-1);
	for(cin>>_;_;_--){
		int n;
		ans.clear();//清空
		scanf("%d",&n);
		fill(used,used+n+2,0);//初始化
		int i,j;
		for(i=2;i<=tot;i++){
			//枚举除2以外的质数
			if(2*prime[i]>n){
				//剪枝
				//不必再继续枚举更大的质数
				break;
			}
			vector<int>prepared;//质数的倍数
			for(j=prime[i];j<=n;j+=prime[i]){
				if(!used[j]){
					//未使用的p的倍数作为备选
					prepared.push_back(j);
				}
			}
			if(prepared.size()&1){
				//奇数个
				//去掉其中一个的偶数
				for(j=0;j<prepared.size();j++){
					if(prepared[j]%2==0){
						prepared.erase(prepared.begin()+j);
						break;
					}
				}
			}
			for(j=0;j<prepared.size();j+=2){
				//两两配对
				used[prepared[j]]=used[prepared[j+1]]=1;
				ans.push_back(prepared[j]);
				ans.push_back(prepared[j+1]);
			}
		}
		vector<int>even;//剩余未使用的偶数
		for(i=1;i<=n;i++){
			if(!used[i]&&i%2==0){
				even.push_back(i);
			}
		}
		for(i=0;i<even.size();i+=2){
			if(i==even.size()-1){
				//若剩余偶数数量为奇数个
				//会枚举到even.size()-1
				//需要break
				break;
			}
			used[even[i]]=used[even[i+1]]=1;
			ans.push_back(even[i]);
			ans.push_back(even[i+1]);
		}
		printf("%d\n",ans.size()>>1);
		for(i=0;i<ans.size();i+=2){
			//两两输出答案
			printf("%d %d\n",ans[i],ans[i+1]);
		}
	}
	return 0;
}
void EulerSieve(int n){
	int i,j;
	for(i=2;i<=n;i++){
		if(!notprime[i]){
			prime[++tot]=i;
		}
		for(j=1;j<=tot&&i*prime[j]<=n;j++){
			notprime[i*prime[j]]=1;
			if(i%prime[j]==0){
				break;
			}
		}
	}
}