HDU 4790 容斥原理 + 数学分析

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;
typedef long long LL;
LL a, b, c, d, p, m;
LL gcd(LL m, LL n)
{
    if(n==0) return m;
    else return gcd(n, m%n);
}

LL get(LL a, LL b)
{
    LL res = 0;
    if(a < b)  swap(a, b);
    if(a<0 || b<0) return 0;
    if(a==0&&b==0) return 0==m?1:0;
    if(b==0)
    {
        if(a-m%p>=0) return (a-m%p)/p+1;
        else return 0;
    }
    LL a1 = m%p;
    LL n1 = (b-m%p)/p+1, n2 = (a-m%p)/p+1, n3 = (a+b-m%p)/p+1;
    if(b-m%p < 0) n1 = 0; if(a-m%p < 0) n2=0; if(a+b-m%p<0) n3=0;
    LL res1 = (a1+1+a1+(n1-1)*p+1)*n1/2;
    //cout<<"res1 = "<<res1<<endl;

    LL res2 = (n2-n1)*(b+1);
    //cout<<"res2 = "<<res2<<endl;

    LL res3 = (a+b-(a1+n2*p)+1+a+b-(a1+(n3-1)*p)+1)*(n3-n2)/2;
    //cout<<"res3 = "<<res3<<endl;
    res = res1 + res2 + res3;
    return res;
}

int main()
{
    int T;
    scanf("%d", &T);
    int kase = 0;
    while(T--)
    {
        cin>>a>>b>>c>>d>>p>>m;
        LL res = get(b, d)-get(a-1, d)-get(b,c-1)+get(a-1,c-1);
        //cout<<res<<endl;
        LL tot = (b-a+1)*(d-c+1);
        LL g = gcd(res, tot);
        //cout<<res<<‘ ‘<<tot<<endl;
        cout<<"Case #"<<++kase<<": ";
        cout<<res/g<<‘/‘<<tot/g<<endl;
    }
    return 0;
}