题意：在[a,b]  [c,d] 之间，和模p等于m的对数

详见代码

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include
         
           5 #define LL long long 6 using namespace std; 7 int T; 8 LL a,b,c,d,p,m; 9 10 LL gcd(LL a, LL b) {11     return b ? gcd(b, a % b) : a;12 }13 14 LL fun(LL x,LL y) {
    //表示0到x区间，0到y区间的组合对数15     LL ret;16     LL ra,rb;17     ra=x%p,rb=y%p;18     ret=(x/p)*(y/p)*p;19     ret+=(ra+1)*(y/p)+(rb+1)*(x/p);20     if(ra>m) {21         ret+=min(m+1,rb+1);22         LL tmp=(m+p-ra)%p;23         if(tmp<=rb) {24             ret+=rb-tmp+1;25         }26     } else {27         LL tmp=(m+p-ra)%p;28         if(tmp<=rb) {29             ret+=min(m-tmp+1,rb-tmp+1);30         }31     }32     return ret;33 }34 int main() {35     scanf("%d",&T);36     int cas=0;37     while(T--) {38         cas++;39         scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&p,&m);40         LL ans=fun(b,d)-fun(a-1,d)-fun(b,c-1)+fun(a-1,c-1);//容斥原理求和41         LL tot=(b-a+1)*(d-c+1);42         if(ans<0)43             ans=0;44 //        printf("ans:%I64d tot:%I64d\n",ans,tot);45         LL l=gcd(ans,tot);46         ans/=l,tot/=l;47         printf("Case #%d: %I64d/%I64d\n", cas, ans, tot);48     }49     return 0;50 }