2021联合省选B卷题解

B卷有 (4) 道题与 (A) 卷相同，新增了两道题，分别为数对与取模。

其他 (4) 道题目参加联合省选2021 A卷题解

Day 1 T1 数对

Description

给出 (n) 个正整数 (a_i)，请你求出有多少个数对 ((i,j)) 满足 (1le i,jle n,i ot=j,a_imod a_j=0)。

(nle 2 imes 10^5,a_ile 5 imes 10^5)

Solution

这道题是真正的签到题，注意到 (a) 的范围仅为 (10^5)，因此我们直接记录下每个值的出现次数，枚举 (a_j) 以及 (a_j) 的倍数 (k) 即可。复杂度为调和级数 (mathcal O(nlog n ))。

注意别忘了 (i ot=j,a_i=a_j) 的情况。

code

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef long long ll;
int n,a[N],ct[N],vis[N],mx;
ll ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),ct[a[i]]++,mx=max(mx,a[i]);
	for(int i=1;i<=n;++i){
		if(vis[a[i]]) continue;
		vis[a[i]]=1;ll ret=0;
		for(int j=a[i]<<1;j<=mx;j+=a[i]) ret+=ct[j];
		ans+=ret*ct[a[i]];
		ans+=1ll*ct[a[i]]*(ct[a[i]]-1);
	}
	printf("%lld
",ans);
	return 0;
}

Day 2 T1 取模

Description

给出 (n) 个正整数 (a_i)，选择不同的三个下标 (i,j,k)，最大化 ((a_i+a_j)mod a_k)。

(nle 2 imes 10^5,a_ile 10^8)

solution

考虑一个 (mathcal O(n^2log n)) 的暴力，暴力枚举 (k)，将其他所有数 (mod) 上一个 (a_k) 后得到 (b) 数组，最大值只有两种情况：

(b_i+b_jgeq a_k)，此时直接选择最大的两个 (b_i) 与 (b_j) 更新答案一定最优
(b_i+b_j<a_k)，枚举 (i) ，那么选择最大的 (<a_k-b_i) 的 (b_j) 来更新答案一定最优，后者可以使用 (lower\_bound) 找到。

考虑优化这个暴力，将 (a) 从小到大排序，从后往前考虑每个 (a) 作为模数，并记录当前的最优解，如果当前的 (ale ans)，那么接下来的 (a) 不可能再更新 (ans) 了，直接 (break)。同时，相同的 (a) 我们只考虑一次。这样一来，我们将只会进行 (mathcal O(log max a_i)) 次暴力检验，下面对这一结论进行证明。

假设我们最终在 (a_{x-1}) 处停止，即 (a_{x-1}le ans<a_x)。

因此有 (forall iin [x,n])，有

[ansge (a_{i-1}+a_{i-2})mod a_ige a_{i-1}+a_{i-2}-a_i ]

故

[a_i-ansge (a_{i-1}-ans)+(a_{i-2}-ans) ]

不妨设 (d_i=a_i-ans)，那么 (d_i>0) ，因此 (d) 至少以斐波那契数列增长的速度进行增长，最多增长 (mathcal O(log max a_i)) 次就停止增长了，复杂度得证。

最终复杂度为(mathcal O(nlog max a_i log n ))。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,a[N],ans,b[N],mx[N];
inline void solve(int s){
	for(int j=1;j<=n;++j) b[j]=a[j]%a[s];
	sort(b+1,b+n+1);
	for(int j=2;j<=n;++j){
		int mx=lower_bound(b+j+1,b+n+1,a[s]-b[j])-b-1;
		if(mx>j) ans=max(ans,b[j]+b[mx]); 
	}
	ans=max(ans,(b[n-1]+b[n])%a[s]);
} 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=n;i>=1;--i){
		if(a[i]<=ans) break;
		if(a[i]==a[i+1]) continue;
		solve(i);
	}
	printf("%lld
",ans);
	return 0;
}