526互联

ARC158（A~D)

发布时间 2023-04-02 20:46:42作者: LuoyuSitfitw

Tasks - AtCoder Regular Contest 158

实际上是114514年前做的来着，非常好的数学题集(\(A\)~\(D\))

A - +3 +5 +7 (atcoder.jp)

  1. 因为我们并不在意\(x_1\),\(x_2\),\(x_3\)真正的数值，只在意它们的相对值，所以原本的操作实际上就是\(-2,+0,+2\)
  2. 所以可以先特判\(x_1\),\(x_2\),\(x_3\)的奇偶性
  3. 因为\(-2+2\)抵消了，所以\(x_1+x_2+x_3\)的和是定值，又因为最终三个数相等，所以\(ans=x_1=x_2=x_3=\frac{x_1+x_2+x_3}{3}\)，这里也特判一下能不能除尽以及奇偶性
  4. 最后的答案就是\(\frac{|x_1-ans|+|x_2-ans|+|x_3-ans|}{4}\)，因为\(+2,-2\)成对出现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x1,x2,x3,ans,t,op;
int main(){
	int T; scanf("%d",&T);
	while(T--){
		scanf("%lld%lld%lld",&x1,&x2,&x3),op=x1%2;
		t=(x1+x2+x3)/3;
		if(x2%2!=op||x3%2!=op||(x1+x2+x3)%3||t%2!=op){ printf("-1\n"); continue; }
		ans=(abs(t-x1)+abs(t-x2)+abs(t-x3))/4;
		printf("%lld\n",ans);
		
	}

	return 0;
}

B - Sum-Product Ratio (atcoder.jp)

为了避免复杂的分类讨论，可以直接对负数和正数排序，然后分别取最小、最大的三个，直接暴力运算即可

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const double INF=2e09;
int n,a[N],b[N],cnt1,cnt2;
int c[N],cnt3;
double ans1=INF,ans2=-INF;
int main(){
	scanf("%d",&n);
	for(int i=1,x;i<=n;++i){
		scanf("%d",&x);
		if(x<0) a[++cnt1]=x;
		else b[++cnt2]=x; 
	}
	sort(a+1,a+cnt1+1),sort(b+1,b+cnt2+1);
	for(int i=1;i<=cnt1;++i) if(i<=3||cnt1-i+1<=3) c[++cnt3]=a[i];
	for(int i=1;i<=cnt2;++i) if(i<=3||cnt2-i+1<=3) c[++cnt3]=b[i];
	for(int i=1;i<=cnt3;++i)
		for(int j=i+1;j<=cnt3;++j)
			for(int k=j+1;k<=cnt3;++k)
				ans1=min(ans1,(1.0*c[i]+1.0*c[j]+1.0*c[k])/(1.0*c[i]*c[j]*c[k])),ans2=max(ans2,(1.0*c[i]+1.0*c[j]+1.0*c[k])/(1.0*c[i]*c[j]*c[k]));
	printf("%.12lf %.12lf",ans1,ans2);
	return 0;
}

C - All Pair Digit Sums (atcoder.jp)

妙蛙种子题，但是\(sb\)眼瞎看成取\(max\)了，鬼知道怎么把那么大两个\(\sum\)看成\(max\)的

\(f(x+y)=f(x)+f(y)-9*k\)，\(k\)为\(x\),\(y\)相加后的进位数

所以\(ans\)先赋值为\(f(x)*2n\)，然后再来减后面这个\(9*k\)

然后对于当前数\(x\)，可以二分找出使得它第\(i\)位进位的数字的个数\(num\)（只需要对所有数按照\(i\)位排序即可），\(ans-=num*9\)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int n; 
ll a[N],ans,pw[N],q[16][N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]); ll t=a[i];
		for(;t;t/=10) ans+=n*2*(t%10);		
	}
	pw[0]=1;
	for(int i=1;i<=15;++i) pw[i]=pw[i-1]*10;
	for(int i=1;i<=15;++i){
		for(int j=1;j<=n;++j) q[i][j]=a[j]%pw[i];
		sort(q[i]+1,q[i]+n+1);
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=15;++j){
			ll x=pw[j]-(a[i]%pw[j]);
			int t=lower_bound(q[j]+1,q[j]+n+1,x)-q[j];
			ans-=(n-t+1)*9;
		}
	}
	printf("%lld",ans);
	return 0;
}

D - Equation (atcoder.jp)

如果当前\(x\),\(y\),\(z\)不满足条件，考虑将\(x\),\(y\),\(z\)换成\(kx\),\(ky\),\(kz\)，如果满足条件，则有：

\[(kx+ky+kz)(k^nx^n+k^ny^n+k^nz^n)(k^{2n}x^{2n}+k^{2n}y^{2n}+k^{2n}z^{2n})\equiv k^{3n}x^{3n}+k^{3n}y^{3n}+k^{3n}z^{3n}(mod\ p) \]

也就是

\[k^{3n+1}(x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n})\equiv k^{3n}(x^{3n}+y^{3n}+z^{3n})(mod\ p)\\ k\equiv \frac{(x^{3n}+y^{3n}+z^{3n})}{(x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n})}(mod\ p) \]

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,p,x,y,z;
mt19937 rd(114514);
int rnd(int l,int r){ return rd()%(r-l+1)+l; }
int power(int x,int y){
	int ans=1;
	for(;y;y>>=1,x=x*x%p) if(y&1) ans=ans*x%p;
	return ans;
}
int Elysia[3];
signed main(){
	srand(time(0));
	int T; scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&n,&p);
		while(114514){
			x=rnd(1,p-3),y=rnd(x+1,p-2),z=rnd(y+1,p-1);
			int t1=power(x,n),t2=power(y,n),t3=power(z,n);
			int a=(x+y+z)%p*(t1+t2+t3)%p*(t1*t1%p+t2*t2%p+t3*t3%p)%p;
			int b=(t1*t1%p*t1%p+t2*t2%p*t2%p+t3*t3%p*t3%p)%p;
			if(a!=b){
				if(!a||!b) continue;
				int k=1ll*power(a,p-2)*b%p; x=x*k%p,y=y*k%p,z=z*k%p;
			}
			Elysia[0]=x,Elysia[1]=y,Elysia[2]=z,sort(Elysia,Elysia+3);
			printf("%lld %lld %lld\n",Elysia[0],Elysia[1],Elysia[2]);
			break;
		}
	}
	return 0;
}