题解 | #买橘子#

这道题要求 $6x+8y=n$ ，其中 $x\geq 0,y\geq 0$ ，对于这道题的 $n\leq 1e5$ ，我们完全可以直接枚举 $y$ 就行，如果 $6\mid n-8*y$ ，那么 $ans=\min(ans,y+(n-8*y)/6)$ 。时间复杂度为 $O(n)$ ，对于 $n\leq 1e5$ 完全足够了。

但是当 $n=1e12$ 级别时，这样暴力枚举显然不行，就需要用到 $exgcd(a,b,\&x,\&y)$ 用来判断是否有解，以及其通解形式。

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;
}

对于 $ax+by=c$ ，第一步是考虑考虑求 $ax+by=\gcd(a,b)$ ，解得特解 $(x_0,y_0)$ ，以及 $g=\gcd(a,b)$ ，这时只要判断 $g\mid c$ ，如果是，那么有解，否则无解。

令 $k=c/g,dx=b/g,dy=a/g$ ，有解的通解形式为 $\begin{cases}x=kx_0+t\times dx\\y=ky_0-t\times dy\end{cases}$ ，这时候我们可以根据需要调整 $(x,y)$ 来满足题目要求，比如这道题我们需要最小化 $x+y$ ，也就是最大化 $y$ ，同时要注意 $x\geq 0,y\geq0$ 。

根据 $x\geq 0,y\geq0$ ，我们可以解出 $t$ 的范围 $-\frac{kx_0}{dx}\leq t\leq \frac{ky_0}{dy}$ ，将最小的 $t$ 带进去，求得一组 $(x,y)$ ，最后答案为 $x+y$ 。

#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")