?

题目大意：给出a,b,c,d,p,m,在[a,b]和[c,d]中分别选一个数x,y。问满足（x+y）%p=m的（x,y）有多少组，求出占总组数的比例

首先，当然是想遍历一遍，统计满足的有多少点，如此便能轻松愉快的解出此题；但是，真的是这样吗？

我们看一下数据范围，范围是10^9，如果两个数加起来，便达到了2*10^9，如果我们遍历一遍，复杂度是o(k) k为10^9/p，这样的话，那一定会超时了。所以这题我们不能用暴力的方法。

那应该怎么做？我们再看一次题目，看起来好像是高中数学学过的几何概型啊！对，就是几何概型。

如果用一些数据测试一下就会发现，满足条件的点其实是分三段，第一段：一个单调递增的等差数列；第二段：一段数值相同的数列；第三段：一段单调递减的等差数列。

如此，我们只需要求出每一段的起点，终点，即可算出整段数列的和（利用等差数列的前n项和公式）。当然，其中免不了一些特例判断。

代码如下：

#include
  
   
#include
   
     #include
    
      #include 
     
       #define N 2000000 using namespace std; long long gcd(long long a,long long b) { return b==0?a:gcd(b,a%b); } int main() { #ifndef ONLINE_JUDGE freopen(D:/in.txt,r,stdin); freopen(D:/my.txt,w,stdout); #endif//ONLINE_JUDGE int T; scanf(%d,&T); for(int t=1;t<=T;t++) { long long a,b,c,d,m,p; scanf(%I64d%I64d%I64d%I64d%I64d%I64d,&a,&b,&c,&d,&p,&m); //cin>>a>>b>>c>>d>>p>>m; long long k1=0,k2=0,k3=0,k4=0,k5=0,k6=0,sum1=0,sum2=0,sum3=0; long long s1=b-a+1,s2=d-c+1; if(s1>s2) { swap(s1,s2);swap(a,c);swap(b,d); } long long mot=s1*s2; long long ans=0; if(m<=b+d&&s1!=1&&s2!=1) { k6=(b+d-m)/p; k5=0; k2=k1-1; k4=k3-1; if(m
      
       k4) k3=k4; sum1=(m+m+(k1+k2)*p-2*(a+c)+2)*(k2-k1+1)/2; sum2=(k4-k3+1)*(b-a+1); sum3=(2*(b+d)-(m+m+(k6+k5)*p)+2)*(k6-k5+1)/2; ans=sum1+sum2+sum3; } else if(s1==1&&s2==1) { if((a+c)%p==m) ans=1; } else if(s1==1) { if(m<=a+d) { k6=(a+d-m)/p; if(m<=a+c) k5=ceil((a+c-m)*1.0/p*1.0); else k5=0; ans=k6-k5+1; } else ans=0; } //cout<
       
        
?