UVALive 4384 Business Cards

题目：

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2385

题意：

有 t t 组询问，每次询问能否用一些a×ba×b的纸片拼成 c×d c × d 的纸片。

t≤105,1≤a,b,c,d≤109 t ≤ 10 5 , 1 ≤ a , b , c , d ≤ 10 9

题解：

有两种情况，一种是纸片全部按同一个方向放置，另一种是纸片按照两个方向放置。

第一种情况很容易检查，第二种情况必然存在一些平行的轴线能将不同方向放置的纸片分隔开，否则必然存在一些位置无法填满。（某人：这似乎是伪证；笔者：证明）

考虑平行于轴线的方向，这条边的长度必须能整除 a a 也能整除bb。

考虑垂直于轴线的方向，这条边的长度必须是 a a 和bb的线性组合，即长度是 ax+by a x + b y 的形式，并且 x,y≥0 x , y ≥ 0 。

不妨设垂直的这条边长度为 n n ，有解则必然(a,b)|n(a,b)|n，利用扩展欧几里得算法可以得到一组解使得 ax′+by′=n a x ′ + b y ′ = n ，但是如果 a≠b a ≠ b ，那么 x′,y′ x ′ , y ′ 之中有一个会小于0。

我们知道通解满足 {x=x′+kb(a,b)y=y′−ka(a,b) { x = x ′ + k b ( a , b ) y = y ′ − k a ( a , b ) ，那么只需要合理的设置 k k ，将小于0的那个系数恰好变正，检查另外一个系数能否非负即可，这个可以转化为询问一个区间里是否存在至少一个整数，可以O(1)O(1)解决。

于是每个询问就在 O(logmax(a,b)) O ( log ⁡ max ( a , b ) ) 的复杂度中解决了。

代码：

#include <cstdio>
typedef long long LL;
int t, a, b, c, d;
int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = ;
        y = ;
        return a;
    }
    int r = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return r;
}
bool check(int x, int a, int b)
{
    int s, t, r = exgcd(a, b, s, t);
    if(x % r)
        return ;
    a /= r;
    b /= r;
    x /= r;
    LL xs = (LL)s * x, xt = (LL)t * x;
    if(xs < )
        return xt / a >= (-xs - ) / b + ;
    if(xt < )
        return xs / b >= (-xt - ) / a + ;
    return ;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        puts(c % a ==  && d % b == 
        || c % b ==  && d % a == 
        || c % a ==  && c % b ==  && check(d, a, b)
        || d % a ==  && d % b ==  && check(c, a, b) ? "YES" : "NO");
    }
    return ;
}