注意如果有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
100000 1
100000 1
但是拿到任意一份能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) 回帖