题解 | #买橘子#

这道题要求，其中，对于这道题的，我们完全可以直接枚举就行，如果，那么。 时间复杂度为，对于完全足够了。

但是当级别时，这样暴力枚举显然不行，就需要用到用来判断是否有解，以及其通解形式。

int exgcd(int a,int b,int& x,int& y){
	if(!b){
		x=1;
		y=0;
		return a;
	}
	int gcd=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return gcd;
}

对于，第一步是考虑考虑求，解得特解，以及，这时只要判断，如果是，那么有解，否则无解。

令，有解的通解形式为，这时候我们可以根据需要调整来满足题目要求，比如这道题我们需要最小化，也就是最大化，同时要注意。

根据，我们可以解出的范围，将最小的带进去，求得一组，最后答案为。

#include <bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int& x,int& y){
	if(!b){
		x=1;
		y=0;
		return a;
	}
	int gcd=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return gcd;
}
int main() {
	int n;
	cin >> n;
	int a=6,b=8,x,y;
	int g=exgcd(a,b,x,y);
	if(n%g!=0){
		cout << -1 << endl;
	}else{
		//(x0,y0)
		int k=n/g;
		x*=k,y*=k;
		int dx=b/g;
		int dy=a/g;
		//x=x0+t*dx
		//y=y0-t*dy
		//最小化x，从x到最小非负整数
		int l=ceil(-1.0*x/dx);
		int r=floor(y/dy);
		if(l>r){
			cout << -1 << endl;
			return 0;
		}
		x=x+l*dx,y=y-l*dy;
		int ans=x+y;
		cout << ans << endl;
	}
	return 0;
	
}
// 64 位输出请用 printf("%lld")