竞赛讨论区 > 这题题目有问题,应该问的是非负且最小的目标数为多少
头像
老朱1234
发布于 2022-04-07 11:08
+ 关注

这题题目有问题,应该问的是非负且最小的目标数为多少

注意如果有x,y使得目标式子小于0,就要跳过

这里提供一组数据:
256 2 100000
100000 1
100000 1

x=400,y=-1200是一组解,此时目标值为:1*400*400+100000*400 + 1*(-1200)*(-1200)+100000*(-1200) = -78400000
但是拿到任意一份能ac的代码,对于上面那组数据,输出的都是正数5343065。

ac代码:
//exeCreate 2022-4-6 8:8:32	

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<cmath>
#include<vector>
#include<set>
#include<queue>

#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(),x.end()

using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
typedef pair<int,int> Pii;
const int maxn=2e5+10,maxm=maxn;
const ll mod=1e9+7,inf=0x3f3f3f3f3f3f3f3f;

//exgcd
void exgcd(ll a,ll b,ll& x,ll &y){
	if(b==0) x=1,y=0;
	else{
		exgcd(b,a%b,x,y);
		ll tx=x,ty=y;
		x=ty,y=tx-(a/b)*ty;
	}
}
//gcd
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}

int main()
{
	ll a,b,c,p1,p2,q1,q2;
	cin>>a>>b>>c>>p1>>p2>>q1>>q2;

	if(c==0) {puts("0");return 0;}
	else{
		if(a==0&&b==0){puts("Kuon");return 0;}
		else if(a*b==0){
			if(a==0&&b!=0)	swap(p1,q1),swap(p2,q2),swap(a,b);
			if(c%a!=0) {puts("Kuon");return 0;}
			ll x = c/a;
			printf("%lld\n",(p2*x+p1)*x);
		}
		else{
			ll x,y;	
			ll cd = gcd(a,b);
			if(c%cd!=0) {puts("Kuon");return 0;}

			exgcd(a,b,x,y);

			x*=c/cd,y*=c/cd;
			ll dx = b/cd,dy = a/cd;

			ll ans = inf;
			while(-p1/p2<=x){
				ll sum=(p2*x+p1)*x+(q2*y+q1)*y;
				if(sum>=0) ans = min(ans,sum);
				x-=dx,y+=dy;
			}
			while(-q1/q2<=y){
				ll sum=(p2*x+p1)*x+(q2*y+q1)*y;
				if(sum>=0) ans = min(ans,sum);
				/*if(ans>(p2*x+p1)*x+(q2*y+q1)*y){
					ans = (p2*x+p1)*x+(q2*y+q1)*y;
					if(x==400) 
						int a=1;
					if(x==500) 
						int a=1;
					if(x==600) 
						int a=1;
				}*/
				x+=dx,y-=dy;
			}
			cout<<ans<<endl;
		}
	}


	fflush(stdin);	getchar();
	return 0;
}
//maxn改好了么?


全部评论

(1) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐