题目链接：JZOJ 3736/Maloyaroslavets Summer Camp 2008。

题目

题目描述

给定两个向量 $\vec{a}=(x _ 1,y _ 1),\vec{b}=(x _ 2,y _ 2)$。求出一对整数 $\lambda _ 1,\lambda _ 2$ 使得 $|\lambda _ 1\vec{a} +\lambda _ 2\vec{b}|$ 最小（ $|\vec{v} |$ 表示向量 $\vec{v}$ 的长度），要求 $\lambda _ 1,\lambda _ 2$ 不同时为 $0$。

输入格式

输入有多组输入有多组测例，每组测例有一行，为 $4$ 个整数 $x _ 1,y _ 1,x _ 2,y _ 2$，含义见题目描述。输入文件以 EOF 结束。

输出格式

对于每组测例，输出一行，为一个整数 $|\lambda _ 1\vec{a}+\lambda _ 2\vec{b}|^2$。

样例输入输出

#1

• Input:

3 0 1 2
6 0 4 0

• Output:

5

样例解释

• 第一组：$\lambda _ 1=0,\lambda _ 2=1$；
• 第二组：$\lambda _ 1=2,\lambda _ 2=3$（多种解法）。

数据范围

设单个测试点的测例组数为 $T$。
$20\%$ 的数据，满足 $T\leq 100$，存在一组最优的 $\lambda _ 1,\lambda _ 2$ 满足 $|\lambda _ 1|,|\lambda _ 2|\leq 30$。
$60\%$ 的数据，满足 $T\leq 10^4$，存在一组最优的 $\lambda _ 1,\lambda _ 2$ 满足 $\min\{|\lambda _ 1|,|\lambda _ 2|\}\leq 30$。
$100\%$ 的数据，满足 $T\leq 10^5,|x _ 1|,|x _ 2|,| y _ 1 |,| y_ 2 |\leq 10 ^ {4}$，存在一组最优的 $\lambda _ 1,\lambda _ 2$ 满足 $\min\{|\lambda _ 1|,|\lambda _ 2|\}\leq 10^4$。

时空限制

$$1000\text{ms}/256\text{MiB}$$

本题有多种解法（模拟两种（20分、60分），水法（100分），数论正解（100）），详情请看下一页。

题解

解法 A （直接模拟）

思路

思路十分简单，面对数据范围的编程思想十分明显。

代码

略

解法 B （优化模拟）

思路

略

代码

考场代码。

#include<cstdio>
#include<algorithm>
using std::min;
typedef long long ll;
#define INF 0X3F3F3F3F3F3F3F3Fll
const int MAXT=100000+5;
ll x1,y1,x2,y2;
int main(void){
    //freopen("math.in","r",stdin);
    //freopen("math.out","w",stdout);
    register int i,j;
    register ll now,last,ans;
    while(scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2)!=EOF){
        ans=INF;
        for(i=-30;i<=30;++i){
            last=INF;
            for(j=1;j<=10000;++j){
                now=(i*x1+j*x2)*(i*x1+j*x2)+(i*y1+j*y2)*(i*y1+j*y2);
                if(now>last)
                    break;
                //printf("%d %d %lld last=%lld\n",i,j,now,last);
                last=now;
                ans=min((ll)ans,(ll)now);
            }
            last=INF;
            for(j=-1;j>=-10000;--j){
                now=(i*x1+j*x2)*(i*x1+j*x2)+(i*y1+j*y2)*(i*y1+j*y2);
                if(now>last)
                    break;
                //printf("%d %d %lld last=%lld\n",i,j,now,last);
                last=now;
                ans=min((ll)ans,(ll)now);
            }
        }
        for(j=-30;j<=30;++j){
            last=INF;
            for(i=1;i<=10000;++i){
                now=(i*x1+j*x2)*(i*x1+j*x2)+(i*y1+j*y2)*(i*y1+j*y2);
                if(now>last)
                    break;
                //printf("%d %d %lld last=%lld\n",i,j,now,last);
                last=now;
                ans=min((ll)ans,(ll)now);
            }
            last=INF;
            for(i=-1;i>=-10000;--i){
                now=(i*x1+j*x2)*(i*x1+j*x2)+(i*y1+j*y2)*(i*y1+j*y2);
                if(now>last)
                    break;
                //printf("%d %d %lld last=%lld\n",i,j,now,last);
                last=now;
                ans=min((ll)ans,(ll)now);
            }
        }
        printf("%lld\n",ans);
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

解法 C （水法：贪心）

很玄学，我也不会，估计是随机化（爬山）吧。

解法 D （数论正解）

思路

我的还没写，先看大佬的论文，如果打不开，可以看这个吧。

代码

代码实现起来比较短，时间复杂度难以分析，根据数据（itdep 的大小）得出算法的运行时间增长缓慢，大致为 $\log _ 2n$ 的级别，所以该算法的时间复杂度应该是 $\Theta(\log _ 2n)$。

#include<cstdio>
typedef long long ll;
int itdep=0;
ll x1,y1,x2,y2;
void Solve(ll,ll,ll,ll,int&,int&);
int main(void){
    //freopen("math.in","r",stdin);
    //freopen("math.out","w",stdout);
    int lambda1,lambda2;
    while(scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2)!=EOF){
        Solve(x1,y1,x2,y2,lambda1,lambda2);
        printf("%lld\n",(lambda1*x1+lambda2*x2)*(lambda1*x1+lambda2*x2)+(lambda1*y1+lambda2*y2)*(lambda1*y1+lambda2*y2));
        //printf("itdep=%d\n",itdep);
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
void Solve(ll a,ll b,ll c,ll d,int &x,int &y){
    ++itdep;//统计步数，试图测量时间复杂度
    ll dot=a*c+b*d;//向量点乘，也就是投影长度
    if(dot<0){//不同方向
        Solve(a,b,-c,-d,x,y);//反向
        y=-y;
        return;
    }
    ll L12=a*a+b*b,L22=c*c+d*d;
    //两个向量模长的平方
    if(L12>L22){//a更长
        Solve(c,d,a,b,y,x);//交换
        return;
    }
    if(dot*dot*4<=L12*L22){//如果夹角大于pi/3
        x=1,y=0;
        return;
    }
    ll k=dot/L12;//对应论文中的k
    if(dot+dot<=L12*(k+k+1)){
        Solve(a,b,c-k*a,d-k*b,x,y);
        x-=k*y;
    }
    else{
        Solve(a,b,c-(k+1)*a,d-(k+1)*b,x,y);
        x-=(k+1)*y;
    }
    return;
}