4
0 5 0 5 3 0
0 999999 0 999999 1000000 0
0 3 0 3 8 7
3 3 4 4 7 0

Case #1: 1/3
Case #2: 1/1000000
Case #3: 0/1
Case #4: 1/1

题目

输入 z1 y1  z2 y2 q m

问 z1到y1 中取一个数   再从 z2到y2中取一个数， 两数加和 对q取模  ，其值等于m的几率是多大

很容易知道总的选择，为(y2-z2+1)*(y1-z1+1)；

然后可以通过容斥原理来算分子

dd=count(y1,y2,q,m);  这个算的是0-y1和0-y2中的任意两数和对q取模答案是m的方法数   为了好记，dd的意义是大大
xd=count(z1-1,y2,q,m);  接下来三个同上  xd意义是 大小
dx=count(z2-1,y1,q,m); 
xx=count(z1-1,z2-1,q,m);

根据容斥原理，可以得到ans=dd-dx-xd+xx

dd因为是从0开始算，所以多算了，-dx-xd可以把有比z1 z2小的那些方法数给去掉，但是去的过程中又多去了 xx，所以把xx加回来

count(__int64 num1,__int64 num2,__int64 q,__int64 m)  

 count可以自己算，想法就是把两个输入的数按q个数拆分，num1这个数按q来分，可以分成rep1段，剩下m1个数字不足q 

__int64 ji(__int64 m1,__int64 m2,__int64 q,__int64 m)

这个函数是计算 有m1个数，比如说m1=4 那第一组数字就是0，1，2，3这四个数字，第二组有m2个数，也是从0开始算的；

这两个数都是比q小的，可以用ji（）这个函数，算出符合要求的方法数；

 
#include<stdio.h>
__int64 ji(__int64 m1,__int64 m2,__int64 q,__int64 m) // m1 m2 是个数  m是目标
{
	__int64 ans=0;
	__int64 tem=q-1-m;// 最多
	if(tem-(q-m1)-(q-m2)>0)
		ans+=tem-(q-m1)-(q-m2); 
	m1--;// 从有几个数字 变成 这个数字剩下数最大多少
	m2--; 
	//没取模
	if(m1>=m&&m2>=m)
	{
		ans+=(m+1);
	}
	else if(m1>=m)
	{
		ans+=m2+1;
	}
	else if(m2>=m)
	{
		ans+=m1+1;
	}
	else
	{
		if(m1+m2>=m)
		{
			ans+=m2-(m-m1)+1;
		}
	}
	return ans;

}
__int64 count(__int64 num1,__int64 num2,__int64 q,__int64 m)//m < p  
{
	__int64 rep1,rep2,ans,m1,m2;
	rep1=(num1+1)/q;
	rep2=(num2+1)/q;
	ans=0;
	ans+=rep1*rep2*(m+1);//前段不取余
	if(m!=q-1)//取余的
		ans+=(q-1-m)*rep1*rep2;
	//尾巴和头的  要加上

	m1=(num1+1)%q;  // 1 -  剩下的个数
	m2=(num2+1)%q;

	ans+=ji(m1,m2,q,m);
	ans+=rep2*ji(m1,q,q,m);
	ans+=rep1*ji(q,m2,q,m);

	return ans; 
} 
__int64 gcd(__int64 n,__int64 m){//最大公因数
	__int64 tmp;
	while(m){tmp=n;n=m;m=tmp%m;}
	return n;
}
int main()
{
	__int64 ans,yue,fenmu;
	__int64 t,z1,y1,z2,y2;
	__int64 q,m,dd,dx,xd,xx;
	__int64 cas=1;

	scanf("%I64d",&t);
	while(t--)
	{
		/*调试用
		printf("0-a 0-b  有多少 匹配 相加%q等于m\n");
		scanf("%I64d%I64d%I64d%I64d",&z1,&z2,&q,&m);
		printf("%I64d\n",count(z1,z2,q,m));
		__int64 i,j,ans=0;
		for(i=0;i<=z1;i++)
		{
			for(j=0;j<=z2;j++)
			{
				if((i+j)%q==m)
					ans++;
			}
		}
		printf("%I64d\n",ans);
		*/
		
		scanf("%I64d%I64d",&z1,&y1);
		scanf("%I64d%I64d",&z2,&y2);
		scanf("%I64d%I64d",&q,&m);
		dd=count(y1,y2,q,m);
		xd=dx=xx=0;
		if(z1!=0)
			xd=count(z1-1,y2,q,m); 
		if(z2!=0)
			dx=count(z2-1,y1,q,m);
		if(z1!=0&&y1!=0)
			xx=count(z1-1,z2-1,q,m);


		//printf("dd%I64d dx%I64d xd%I64d xx%I64d\n",dd,dx,xd,xx);
		fenmu=(y2-z2+1)*(y1-z1+1);//总的
		ans=dd-dx-xd+xx;
		yue=gcd(ans,fenmu);
		printf("Case #%I64d: ",cas++);
		if(ans==0)
		{
			puts("0/1");
		}
		else
			printf("%I64d/%I64d\n",ans/yue,fenmu/yue);
	}
	return 0;
}

4
0 5 0 5 3 0
0 999999 0 999999 1000000 0
0 3 0 3 8 7
3 3 4 4 7 0

Case #1: 1/3
Case #2: 1/1000000
Case #3: 0/1
Case #4: 1/1

hdu 4790 Just Random 容斥原理+数学

原文：http://blog.csdn.net/u013532224/article/details/40984799