hdu 4790 Just Random 神奇的容斥原理
发布日期:2021-08-10 12:42:02 浏览次数:7 分类:技术文章

本文共 2690 字,大约阅读时间需要 8 分钟。

1 /** 2 大意: 给定[a,b],[c,d]  在这两个区间内分别取一个x,y  使得 (x+y)%p = m  3 思路:res = f(b,d) -f(b,c-1)-f(a-1,d)+f(a-1,c-1);   f(b,d ) 表示在[0,b],[0,d] 之间有多少个符合上述要求的数     4           1、将[0,b] 分为两部分, b/p  和 b%p  能整除p的[0,(b/p)*p] 和[(b/p)*p+1,b ]  同理[0,d]也可以这样分, 这样对于[0,b]  [0,d ] 分别有两种情况,则一共有四种情况。 5 a、 对于能整除的部分,直接相乘可得结果ans += (b/p)*(d/p)*p; 6 b、 对于b 不能整除的和 d 能整除的。。 ans += (b%p+1)*(d/p) 7 c、 对于d不能整除的和b能整除的。   ans += (d%p+1)*(b/p) 8 d 、 对于 b不能整除和d也不能整除的。。 9 先举下面一个例子10 11 对于一个完整的区间来说,不难想到[0,m]对应[m,0],那么对于[m+1,p-1]对应哪一个区间呢,一个数a来说,如果a%p=m,则a=m,m+p,m+2*p……由于[0,p-1]中任意两个数的和都小于2*p,因此a只能为m或者m+p,那么[m+1,p-1]就对应着[p-1,m-1]。下面是m=3,p=8的情况12             0      1       2         3         4         5          6          713             3      2       1         0         7         6          5          4          14 15 那么。。ma = b%p  mb = d%p。。。16 若是ma〉m  那么:17         ans += min(m+1,mb+1);18         tmp = (p+m-ma)%p;19         if(tmp<=mb) ans += (mb-tmp+1);20 21 若是ma〈 m 那么:22         tmp = (m-ma+p)%p;23         if(tmp<=mb)24             ans += min(m-tmp+1,mb-tmp+1);25 **/26 27 别人的解释。。。28 总的组合数很容易算出来,也就是两个区间的整数的个数的乘积。接下来是求两个数的和,对于一个区间,我们可以根据区间模p的结果进行划分:[a%p,p-1],[0,p-1],[0,b%p],也就是说把区间中前面和后面不完整的[0,p-1]的区间单独拿出来分析,中间的完整的一起算就好了。接下来是区间中模p等于m的数的个数,对于一个完整的区间来说,不难想到[0,m]对应[m,0],那么对于[m+1,p-1]对应哪一个区间呢,一个数a来说,如果a%p=m,则a=m,m+p,m+2*p……由于[0,p-1]中任意两个数的和都小于2*p,因此a只能为m或者m+p,那么[m+1,p-1]就对应着[p-1,m-1]。下面是m=3,p=8的情况29             0      1       2         3         4         5          6          730             3      2       1         0         7         6          5          4          31 这样一个完整的区间中两个数的和对p取模等于m的对应关系就确定了。接下来就是分区间讨论,对于完整的区间可以完全对应,因此是p,对于不完整的区间,算出它对应的区间,然后跟另一个区间比较,看覆盖的长度就行了。这题想到这应该就没问题了,但是写起来还是挺容易错的。32 33 34 #include 
35 #include
36 using namespace std;37 long long a,b,c,d,p,m;38 39 long long min(long long a,long long b){40 return a
m){54 ans += min(m+1,mb+1);55 tmp = (p+m-ma)%p;56 if(tmp<=mb) ans += (mb-tmp+1);57 }else{58 tmp = (m-ma+p)%p;59 if(tmp<=mb)60 ans += min(m-tmp+1,mb-tmp+1);61 }62 return ans;63 }64 65 long long gcd(long long a,long long b){66 if(b==0)67 return a;68 return gcd(b,a%b);69 }70 71 int main()72 {73 int t;74 cin>>t;75 int cnt;76 for(cnt=1;cnt<=t;cnt++){77 cin>>a>>b>>c>>d>>p>>m;78 long long res;79 res = sol(b,d)-sol(b,c-1)-sol(a-1,d)+sol(a-1,c-1);80 long long sum =(long long ) ((b-a+1)*(d-c+1));81 long long gcdD = gcd(res ,sum);82 // cout<
<<"------------>"<
<

 

转载于:https://www.cnblogs.com/Bang-cansee/p/3724060.html

转载地址:https://blog.csdn.net/weixin_30588729/article/details/97859501 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:一次下载多个文件的解决思路-JS
下一篇:android 种的WiFi相关

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.207.175.100]2024年03月27日 01时13分03秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

linux 模拟键盘输入到进程,Linux 下模拟键盘输入 2019-04-21
linux服务器上已安装R 用户下载R包,R语言安装R package的2种方法 2019-04-21
linux 7 磁盘空间太小,Linux下磁盘保留空间的调整,解决df看到的空间和实际磁盘大小不一致的问题... 2019-04-21
linux下mysql 备份方法,Linux下mysql数据库备份方法小结 2019-04-21
bootstrap 页面垂直居中_iframe中如何让layer提示框显示在垂直居中的位置 2019-04-21
肺部ct重建_胸片检查容易漏诊肺癌,去年正常今年晚期常发生,体检一定要做CT... 2019-04-21
3dmax如何拆分模型_3D建模大佬如何制作出惊艳四方的游戏建模,看完这篇文章我知道了... 2019-04-21
x86so文件装换成arm64位_64位系统正式发布说明及介绍!! 2019-04-21
for循环中取出最大最小 累加_LeetCode之长度最小的子数组 2019-04-21
如何打开老公人脸识别_【话题】南宁已有小区启用人脸识别门禁,有人点赞有人忧... 2019-04-21
makex机器人程序_机器人教育为相城青少年叩开科学世界大门 2019-04-21
一寸照纯红色底图片_Ella陈嘉桦也是“时髦精”,穿玫红色西装配拼色半身裙,高级洋气... 2019-04-21
米哈游客户端笔试题_Garena校招 游戏客户端开发通关面经 2019-04-21
airpodspro没有弹窗_使用AirPods Pro一天的主观感受 2019-04-21
创建物化视图commit_视图及范式 2019-04-21
函数传参字典_Python新手上车17:函数传递任意多个参数 2019-04-21
去掉数组最后一个元素_【一天一大 lee】在排序数组中查找元素的第一个和最后一个位置 (难度:中等) Day20201201... 2019-04-21
秦九韶算法递推公式_算法讲解之复杂度分析 2019-04-21
添加绝对路径_网站中如何添加绝对路径 2019-04-21
python房价数据分析波士顿代码数据_python数据分析-波士顿房价预测-Go语言中文社区... 2019-04-21