80pts 精度求调!
查看原帖
80pts 精度求调!
550074
cloudemakers楼主2023/8/22 13:44

最后两个WA了 下载数据后发现只相差1 那么是不是哪里的精度不够? Code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y){
	if (b==0){x=1;y=0;return a;}
	ll d=exgcd(b,a%b,x,y);
	ll z=x;x=y;y=z-y*(a/b);
	return d;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main(){
	ll t,a,b,c,x,y;
	scanf("%lld",&t);
	while (t--){
		scanf("%lld%lld%lld",&a,&b,&c);
		ll d=exgcd(a,b,x,y);//方程=gcd(a,b)=d 
		if (c%d!=0){
			printf("-1\n");
			continue;
		}
		double x_=b/d,y_=a/d,k_=c/d;//同时×k 除以d和乘d约去 等于c 
		x=(ll)x*k_;y=(ll)y*k_;
		ll minn=ceil((double)(1-x)/x_),maxx=floor((double)(y-1)/y_);
		if (minn>maxx){
			ll ans1=x+minn*x_,ans2=y-maxx*y_;
			printf("%lld %lld\n",ans1,ans2);
			continue;
		} 
		else{
			ll ans1=maxx-minn+1,ans2=x+minn*x_,ans3=y-maxx*y_,ans4=x+maxx*x_,ans5=y-minn*y_;
			printf("%lld %lld %lld %lld %lld\n",ans1,ans2,ans3,ans4,ans5);
			continue;
		}//此时保证在minn到maxx范围内为正整数解 
	}
	return 0; 
}
2023/8/22 13:44
加载中...