给出一个A和B 想要找到一个X和Y使得 \(A+X|B+Y\).同时使得X+Y最小求出X+Y的最小值。

值域是\([1,10^9]\) 直接枚举X不太行会被某种数据卡掉。

考虑正解：先固定K 另\(\frac{B+Y}{A+X}=K\)

\(Y=AK+XK-B\) 此时由于K已知只需要满足条件\(X>=0,Y>=0\)来求X+Y的值

\(Y>=0\)即\(AK+XK-B>=0\) 解得\(X>=\frac{B}{K}-A\) 这个要和\(X>=0\)取交。

同时X还是一个整数上式显然可以变为\(X>=\frac{B-1}{K}-A+1\)此时除法就是向下取整了。

此时想让X+Y最小就是令X最小那么X取\(max(\frac{B-1}{K}-A+1,0)\)就可以令X+Y达到最小值。

考虑枚举K,\(\frac{B-1}{K}\) 只有根号个取值。

设\(C=max(0,\frac{B-1}{K}-A+1)\) \(X+Y=(K+1)C+AK-B\)

这里对于每个C来说K是自变量\(X+Y=K(C+A)+C-B\)即对于某个C对应的K的集合里最小的K满足最优。

进一步的设\(Q=\frac{B-1}{K}\) 显然最小的K为\(\frac{B-1}{Q+1}+1\)

当然这个没什么用在整除分块的时候可以直接由上次的边界推出来K.

code 
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cctype>
#include<queue>
#include<deque>
#include<stack>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 1000000000
#define inf 100000000000000000ll
#define ldb long double
#define pb push_back
#define put_(x) printf("%d ",x);
#define get(x) x=read()
#define gt(x) scanf("%d",&x)
#define gi(x) scanf("%lf",&x)
#define putl(x) printf("%lld\n",x)
#define rep(p,n,i) for(ll i=p;i<=n;++i)
#define go(x) for(ll i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define pii pair<ll,ll>
#define mk make_pair
#define P 1000000007ll
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define uint unsigned long long
#define ui unsigned
#define sq sqrt
#define a(x) t[x].a
#define sum(x) t[x].sum
#define b(x) t[x].b
#define F first
#define S second
#define mod 998244353
#define sc(A) scanf("%lld",&A);
#define put(A) printf("%d\n",A);
#define add(x,y,m) ((x)+(y)>=m?(x)+(y)-(m):(x)+(y))
using namespace std;
const ll MAXN=5010,maxn=410;
ll T;
signed main()
{
	freopen("1.in","r",stdin);
	sc(T);
	while(T--)
	{
		ll A,B,D,C;
		sc(A);sc(B);D=B-1;
		if(B%A==0){puts("0");continue;}
		if(B<A){put(A-B);continue;}
		ll l,r=0;
		ll ans=INF;
		for(ll i=1;i<=D;i=r+1)
		{
			l=(D/i);
			C=max(0ll,l-A+1);
			ans=min(ans,(C+A)*(r+1)+C-B);
			//if((C+A)*(r+1)+C-B<0)cout<<r<<endl;
			r=D/l;
		}
		putl(ans);
	}
	return 0;
}

原文地址：http://www.cnblogs.com/chdy/p/16791327.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性