wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
LYOJ 219「雅礼集训 2017 Day11」DIV
? solution ?
? 数论 ?
2017-03-25 19:47:20
670
0
0
wuvin
? solution ?
? 数论 ?
## 题目描述 定义复数 $a + bi$ 为整数 $k$ 的约数，当且仅当 $a$ 和 $b$ 为整数且存在整数 $c$ 和 $d$ 满足 $(a + bi)(c + di) = k$，给定 $n$，求出 $1$ 到 $n$ 的所有满足 $a > 0$ 的约数 $a + bi$ 的 $a$ 的和。答案模 $1004535809$ 输出。 ## 输入格式 一行一个整数 $n$。 ## 输出格式 一行一个整数表示答案。 ## 样例 ### 样例输入 1 5 ### 样例输出 1 35 ### 样例输入 2 1000 ### 样例输出 2 1752541 ### 样例输入 3 1000000 ### 样例输出 3 636408476 ## 数据范围与提示 $5\%,n \leq 10$ $10\%,n \leq 50$ $30\%,n \leq 500$ $40\%,n \leq 5000$ $60\%,n \leq 10^7$ $100\%,n \leq 10^{10} $ ## 题解 <br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br> 这是一道简单数论题。 首先分析一下虚数条件是什么意思 即 $$ ac-bd=x\\ ad+bc=0\\ a:b=c:-d $$ 也就是$a,b$和$c,d$分别约去最大公约数以后满足$a=c,b=-d$ 带回得到 $$ k*(a^2+b^2)=x $$ 其中$k=gcd(a,b)*gcd(c,d)$。 那么我们可以得出$a$是$x$的约数当且仅当存在$b(b>0)$使得$a^2+b^2=x_1(x=k*x_1)$或者$a$是$x$的因数。 那么可以下底分块求出$a$是$x$的因数的情况，另一种情况$a<\sqrt{x}$且$x\%a \ne 0 $,可以莫比乌斯反演或者容斥就出。
上一篇:
LYOJ 217 「雅礼集训 2017 Day11」TRI
下一篇:
LYOJ 216 「雅礼集训 2017 Day10」拍苍蝇
0
赞
670 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册