Hihocoder1456 Rikka with Lattice
众所周知,萌萌哒六花不擅长数学,所以勇太给了她一些数学问题做练习,其中有一道是这样的:
勇太有一个$n times m$的点阵,他想要从这$n times m$个点中选出三个点 ${A,B,C}$,满足:
- 三角形$ABC$面积不为$0$且其内部不存在整点。
- 边$AB$,$BC$,$CA$上不存在除了端点以外的整点。
现在勇太想要知道有多少种不同的选取方案满足条件。
当然,这个问题对于萌萌哒六花来说实在是太难了,你可以帮帮她吗?
注意${A,B,C}$与${B,A,C}$视为同一种方案。
$n,m leqslant 5 times 10^9$。
题解
一道比较有趣的数论题。看范围应该能猜到是杜教筛一类的东西,但是推不出第一步的式子啊= =
首先考虑题目这个奇怪的条件,其实由皮克定理,我们可以得到,这个三角形的面积为$frac{1}{2}$,也就是说,题目要求的就是面积为$frac{1}{2}$的三角形的个数。
考虑这种三角形大概长什么样子,然后你会发现它只能长成这样:
考虑一个$a times b$的矩形,以这个矩形的两个相对的点为其中两个顶点的三角形的个数。设$vec{BE}$的坐标为$(x,y)$那么这个三角形的面积就可以表示为:
$$S=frac{1}{2}|vec{BE} times vec{BD}|=frac{1}{2}|ay-bx|$$
令$S=frac{1}{2}$,则有$ay-bx=pm 1$。
由裴蜀原理,这个方程仅在$gcd(a,b)=1$时有解,且每个方程恰好有一组解。再把对角线换一下,于是当$gcd(a,b)=1$时,会有$4$个这样的三角形。
然后这个奇怪的题,终于被我们化成了这样的式子:
$$sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j)=1]4(n-i)(m-j)$$
莫比乌斯反演一下,就变成这样了:
$$4 sum_{x=1}^{min(n,m)} mu(x) sum_{i=1}^{lfloor frac{n}{x} rfloor} sum_{j=1}^{lfloor frac{m}{x} rfloor} nm - mix - njx + ijx^2$$
令$S(n)=sum_{i=1}^{n}i=frac{n(n+1)}{2}$把式子再化简一下,就变成:
$$4 sum_{x=1}^{min(n,m)} mu(x)(lfloor frac{n}{x} rfloor lfloor frac{m}{x} rfloor nm-x lfloor frac{m}{x} rfloor S(lfloor frac{n}{x} rfloor)-x lfloor frac{n}{x} rfloor S(lfloor frac{m}{x} rfloor)+x^2 S(lfloor frac{m}{x} rfloor) S(lfloor frac{n}{x} rfloor))$$
终于,这个式子的求法很显然了,可以直接枚举,$O(n)$计算。然而这还是过不了,得加上杜教筛。
这里杜教筛要筛的东西还挺多的,一个是$sum_{i=1}^{n}mu(i)$,一个是$sum_{i=1}^{n}mu(i)i$,还要筛出$sum_{i=1}^{n}mu(i)i^2$。
关于这三个函数的筛法,我都在这里讲一下:
关于杜教筛,我们知道有个这样的式子:
$$L(n)-g(1)F(n)=sum_{i=2}^n g(i) F(lfloorfrac{n}{i}rfloor)$$
其中$f*g=l$。
对于$sum_{i=1}^{n}mu(i)$,我们是令$g=1$,利用$sum_{d|n}mu(d)=[n=1]$,于是使得$L(n)=1$,从而完成计算;
对于$sum_{i=1}^{n}mu(i)i$,我们则令$g(i)=i$,那么$sum_{d|n}mu(d)d times frac{n}{d}=1$,从而$L(n)=1$,从而实现了杜教筛;
对于$sum_{i=1}^{n}mu(i)i^2$,类似地,我们令$g(i)=i^2$,那么$sum_{d|n}mu(d)d^2 times (frac{n}{d})^2=1$,从而$L(n)=1$,从而也实现了杜教筛;
由于$5 times 10^9 times 5 times 10^9=2.5 times 10^{19}$超过了long long
的范围,因此取模变得很恶心,时常要记得取模。
偷懒用了std::map
,所以时间复杂度$O(n^{frac{2}{3}}logn)$。
代码
|
|
最新文章
- 我的第一篇blog
- C++ 中的sort排序用法
- 3173: [Tjoi2013]最长上升子序列
- Jquery表格变色 复选框全选,反选
- Android - 定时服务 - Timer
- SimpleDateFormat格式化日期
- Content-Disposition的使用和注意事项(转载)
- 使用myeclipse生成的HibernateSessionFactory的合理性
- Special Subsequence(离散化线段树+dp)
- C# 计算器 如果设置键盘输入的监听事件
- ubuntu 安装jdk7总结
- 201521123055 《Java程序设计》第3周学习总结
- 数据结构基础(3) --Permutation &; 插入排序
- 微信小程序-WebSocket应用
- 关于现在互联网是否还有机会类的价值文章,为什么有人掉进互联网创业的坑里,可能因为ta不懂这些
- 个人博客Week3——案例分析
- 移动端适配js
- Ubuntu 14.10 下安装伪分布式hbase 0.99.0
- 4. Tomcat内存溢出解决
- Redis:按照正则批量删除key
热门文章
- 了解SSL证书从HTTPS开始 开发者绕不开的“劫”
- 安装 texlive
- mysql统计指定数据库的各表的条数
- 一篇文章带你了解axios网络交互-Vue
- crf多表与基表系列化-自定义序列化深度表查询-断关联表关系-多表反序列化
- 类似postman插件
- SAP 配置表记录创建人/创建日期/创建时间/更改人/更改日期/更改时间
- netstat - 系统信息
- 吴裕雄--天生自然 JAVA开发学习:文档注释
- 一个http的Post请求问题,unable to resolve host <;我的域名>;:no address associated with hostnam