(HDU4790)Just Random

发表于 | 分类于 ，

原题链接

思路:

将给出的两个数组按照余数放入$[0,p-1]$的”桶”中, 如图所示, 其中ma和mc分别代表a%p, c%p.

这样, 从ma开始,后面(b-a+1)%p个桶中有$\lfloor \frac{b-a+1}{p} \rfloor + 1$个数, 其他的桶中有$\lfloor \frac{b-a+1}{p} \rfloor$.

以$[a,b]$划分的桶作为”基准”, 从ma开始, 可以计算得与其对应的符合$(x+y) \equiv m (mod\ p)$的位置为m-a所在的桶, 即为桶(mc+m-a)%p

得到了起始位置后便可以通过循环来计算符合条件的数字对的数量. 即第一个堆往后遍历, 第二个堆往前遍历.

然而$10^{9}$的数据量直接循环可能会超时, 可以将”桶”分为几个区间, 用区间的分界点来界定需要增加的量.

剩下的操作便是繁琐的细节问题了.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>

long long gcd(long long x,long long y) {
    return y==0 ? x : gcd(y,x%y);
}

int main() {
    int T;
    scanf("%d",&T);
    for(int t(1);t<=T;++t) {
        long long a,b,c,d,p,m;
        scanf("%lld %lld %lld %lld %lld %lld",&a,&b,&c,&d,&p,&m);
        long long ma = a%p, mc = c%p;
        long long ca = (b-a+1)/p, cc = (d-c+1)/p;
        long long pa = (b-a+1)%p, pc = (d-c+1)%p;
        long long ans(0);   //答案
        long long pj((2*p+m-ma-mc)%p);  //第二堆的起始位置
        long long pi(0);
        for(;pi!=p;) {
            long long dpa(pa-pi),dpc(pj-pc+1);  //两个堆与中间分割点的距离
            long long dma(p-pi),dmc(pj+1);  //两个堆与结尾的距离
            /* 判断所在分段 */
            if(dpa>0) {
                if(dpc>0) {
                    if(dpa>dpc) {
                        ans += 1ll*dpc*cc*(ca+1);
                        pi += dpc;
                        pj = pc-1;
                    } else {
                        ans += 1ll*dpa*cc*(ca+1);
                        pi = pa;
                        pj -= dpa;
                    }
                } else {
                    if(dpa>=dmc) {
                        ans += 1ll*dmc*(cc+1)*(ca+1);
                        pi += dmc;
                        pj = p-1;
                    } else {
                        ans += 1ll * dpa * (cc + 1) * (ca + 1);
                        pi = pa;
                        pj -= dpa;
                    }
                }
            } else {
                if(dpc>0) {
                    if(dma>dpc) {
                        ans += 1ll*dpc*cc*ca;
                        pi += dpc;
                        pj = pc-1;
                    } else {
                        ans += 1ll*dma*cc*ca;
                        pi = p;
                        pj -= dma;
                    }
                } else {
                    if(dma>=dmc) {
                        ans += 1ll*dmc*(cc+1)*ca;
                        pi += dmc;
                        pj = p-1;
                    } else {
                        ans += 1ll*dma*(cc+1)*ca;
                        pi = p;
                        pj -= dma;
                    }
                }
            }
            if(pj<0) {
                pj += p;
            }
        }
        long long tot = 1ll*(b-a+1)*(d-c+1),g(gcd(tot,ans));
        printf("Case #%d: %lld/%lld\n",t,ans/g,tot/g);
    }
    return 0;
}