题解 P1450 【[HAOI2008]硬币购物】

· · 题解

既然没人写扩欧，那我就来一发吧。

扩欧也还好，就是跑的有点慢，然后写的时候还有点烦，不过还是卡过去了。

考场上看到这道题又蒙了。。。 怎么回事第一题又要爆零了？

然后我打了个暴力测了一下极限数据根本过不去（幸好没把电脑整死机）

于是想了又想，整出了个 O(s* t)的扩欧算法（打了一个小时的样子）。

（话说正解好像容斥）

原本搞了下循环展开结果好像会更慢。。。

讲一下思路：用扩欧解。

安利扩欧博客：Judge's Class

预处理解之前我们要先用扩欧求出:
c1*x + c2*y = gcd(c1,c2) 中的 x和y （以及gcd），记录下来，
然后 c1、c2 除以 gcd(c1,c2)。（会扩欧的话就能懂吧。）
然后我们先 O(s log s) 预处理用 c1、c2 能拼出 s 的解。
（即 c1*x1 + c2*y1 = s 中 x1和y1 的解）
然后我们令 x1 达到最小正整数状态，即 y1 达到最大解。
这时如果 y1 为负数，则无解，将数组中的值设为-1，break。
否则我们用数组记录下此时的解。

那么 c3、c4 也是同理这样处理。

这样处理完之后我们发现如果没有 d 数组的限制，y/c2 就是方案数，
那么我们考虑一下 d1对x1 的限制 以及 d2 对 y1 的限制求出解的方案数。
然后记录答案在 f 数组里面，至于 c3、c4 就记录进 g 数组。
然后 O(s) 滚出答案。
//by Judge
#include<bits/stdc++.h>
#define rint register int
#define ll long long
using namespace std;
const int M=1e5+5;
#idndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1,*p2;
inline int read(){ int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} int c1,c2,c3,c4,d1,d2,x11,x22,y11,y22,d[5];
int X1[M],X2[M],Y1[M],Y2[M],f[M],g[M];
int ex_gcd(int a,int b,int& x,int& y){ /* 套个板子，忘了就现推 */
    if(!b) return x=1,y=0,a;
    int d=ex_gcd(b,a%b,y,x);
    return y-=a/b*x,d;
}
int main(){
    c1=read(),c2=read();
    c3=read(),c4=read();
    d1=ex_gcd(c1,c2,x11,y11);
    d2=ex_gcd(c3,c4,x22,y22);
    c1/=d1,c2/=d1,c3/=d2,c4/=d2;
    /*  预处理出解  */
    for(rint s=1;s<=1e5;++s){
        rint tmp=s,x=x11,y=y11;
        rint a=c1,b=c2;
        if(tmp%d1){
            X1[s]=Y1[s]=-1;
            continue;
        }
        tmp/=d1,x*=tmp,y*=tmp;

        y+=x/b*a,x%=b;
        if(x<0) x+=b,y-=a;
        if(y>=0) X1[s]=x,Y1[s]=y;
        else X1[s]=Y1[s]=-1;
    }
    for(rint s=1;s<=1e5;++s){
        rint tmp=s,x=x22,y=y22;
        rint a=c3,b=c4;
        if(tmp%d2){
            X2[s]=Y2[s]=-1;
            continue;
        }
        tmp/=d2,x*=tmp,y*=tmp;

        y+=x/b*a,x%=b;
        if(x<0) x+=b,y-=a;
        if(y>=0) X2[s]=x,Y2[s]=y;
        else X2[s]=Y2[s]=-1;
    }
    for(rint T=read(),S;T;--T){
        ll ans=0;
        for(int i=1;i<=4;++i)
            d[i]=read();
        S=read(),f[0]=g[0]=1;
        /*  考虑限制求出方案数  */
        for(rint s=1;s<=S;++s){
            rint tmp=s,a=c1,b=c2;
            rint x=X1[s],y=Y1[s];
            if(x<0||y<0){
                f[s]=0;
                continue;
            }
            rint maxX=min(x+y/a*b,d[1]);

            if(d[2]<y) x+=(y-d[2]+a-1)/a*b;
            if(x>maxX){
                f[s]=0;
                continue;
            }
            f[s]=(maxX-x)/b+1;
        }
        for(rint s=1;s<=S;++s){
            rint tmp=s,a=c3,b=c4;
            rint x=X2[s],y=Y2[s];
            if(x<0||y<0){
                g[s]=0;
                continue;
            }
            rint maxX=min(x+y/a*b,d[3]);

            if(d[4]<y) x+=(y-d[4]+a-1)/a*b;
            if(x>maxX){
                g[s]=0;
                continue;
            }
            g[s]=(maxX-x)/b+1;
        }
        /*  O(s) 滚出答案  */
        for(rint i=0;i<=S;++i)
            ans+=1ll*f[i]*g[S-i];
        printf("%lld\n",ans);
    } return 0;
}