hdu 4790 Just Random

思路：对于a<=x<=b,c<=y<=d，满足条件的结果为ans=f(b,d)-f(b,c-1)-f(a-1,d)+f(a-1,c-1)。

而函数f(a,b)是计算0<=x<=a,0<=y<=b满足条件的结果。这样计算就很方便了。

例如：求f(16,7),p=6,m=2.

对于x有：0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4

对于y有：0 1 2 3 4 5 0 1

很容易知道对于xy中的（0 1 2 3 4 5）对满足条件的数目为p。

这样取A集合为（0 1 2 3 4 5 0 1 2 3 4 5），B集合为（0 1 2 3 4）。

C集合为（0 1 2 3 4 5），D集合为（0 1）。

这样就可以分成4部分来计算了。

f(16,7)=A和C满足条件的数+A和D满足条件的数+B和C满足条件的数+B和D满足条件的数。

其中前3个很好求的，关键是B和D满足条件的怎么求！

这个要根据m来分情况。

#include<cstdio>

#include<iostream>

using namespace std;

#define ll __int64

ll p,m;

ll gcd(ll a,ll b)

{

    if(a<b) swap(a,b);

    while(b){

        ll t=a;

        a=b;

        b=t%b;

    }

    return a;

}

ll f(ll a,ll b)

{

    if(a<||b<) return ;

    ll ma=a%p,mb=b%p,ans;

    ans=(a/p)*(b/p)*p;//

    ans+=(ma+)*(b/p)+(mb+)*(a/p);//2+3

    if(ma>m){ //

        ans+=min(m,mb)+;

        ll t=(p+m-ma)%p;//根据ma求出满足最小的y来

        if(t<=mb) ans+=mb-t+;

    }else{

        ll t=(p+m-ma)%p;//根据ma求出满足最小的y来

        if(t<=mb) ans+=min(m-t+,mb-t+);

    }

    return ans;

}

int main()

{

    int ca=,t;

    ll a,b,c,d;

    scanf("%d",&t);

    while(t--){

        cin>>a>>b>>c>>d>>p>>m;

        ll ans=f(b,d)-f(b,c-)-f(a-,d)+f(a-,c-);

        ll tot=(b-a+)*(d-c+);

        ll g=gcd(ans,tot);

        printf("Case #%d: %I64d/%I64d\n",++ca,ans/g,tot/g);

    }

    return ;

}

巴特西

hdu 4790 Just Random

最新文章

热门文章