ABC315 G扩欧班子球调
  • 板块学术版
  • 楼主_lqs_
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/8/20 16:43
  • 上次更新2023/11/3 02:26:13
查看原帖
ABC315 G扩欧班子球调
664744
_lqs_楼主2023/8/20 16:43

AC 49,WA 52,边界调了一年也没调出来。

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define int long long
int n,m,i,j,ans,a,b,c,x,l,r;
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
void exgcd(int a,int b,int c){
	if(b==0){
		l=c/a,r=0;
		return;
	}
	exgcd(b,a%b,c);
	int tmp=l;
	l=r,r=tmp-a/b*r;
}
signed main(){
	scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&x);
	for(i=1;i<=n;i++){
		int k=x-a*i,d=gcd(b,c);
		if(k%d!=0 || k<=0) continue;
		exgcd(b,c,k);
		int L=c/d,R=b/d;
		l%=L;
		if(l==0) l+=L;
		r=(k-b*l)/c;
		if(r<=0) continue;
		if(r>n){
			if((r-n)%R==0) r=n;
			else r=r-((r-n)/R+1)*R;
			l=(k-c*r)/b;
			if(l>n || r<=0) continue;
		}
		int p1=0,p2=0;
		if(r%R==0) p1=r/R;
		else p1=r/R+1;
		if((n-l)%L==0) p2=(n-l)/L+1;
		else p2=(n-l)/L+1;
		ans+=min(p1,p2);
//		printf("%d\n",ans);
	}
	printf("%lld\n",ans);
	return 0;
}
2023/8/20 16:43
加载中...