【BZOJ】2956: 模积和
题意
求\(\sum_{i=1}^{n} \sum_{j=1}^{m} (n \ mod \ i)(m \ mod \ j)[i \neq j] \ mod \ 19940417\), \((n, m \le 10^9)\)
分析
以下均设\(n \le m\)
$$
\begin{align}
&
\sum_{i=1}^{n} \sum_{j=1}^{m} (n \ mod \ i)(m \ mod \ j)[i \neq j] \ mod \ 19940417
\\
\equiv &
\left(
\sum_{i=1}^{n}
\sum_{j=1}^{m}
(n \ mod \ i)(m \ mod \ j)
\sum_{i=1}^{n}
(n \ mod \ i \cdot m \ mod \ i)
\right)
\ mod \ 19940417
\
\equiv &
\left(
\left(
\sum_{i=1}^{n}
(n \ mod \ i)
\right)
\left(
\sum_{j=1}^{m}
(m \ mod \ i)
\right)
\sum_{i=1}^{n}
(n \ mod \ i \cdot m \ mod \ i)
\right)
\ mod \ 19940417
\
\end{align}
于是我们只需要快速求出$\sum_{i=1}^{n} ( n \ mod \ i)$和$\sum_{i=1}^{n} ( n \ mod \ i \cdot m \ mod \ i )$就能解决问题了。
<p>
\]
\begin{align}
& \sum_{i=1}^{n} ( n \ mod \ i)
\
= &
\sum_{i=1}^{n}
\left( n - i \left \lfloor \frac{n}{i} \right \rfloor \right)
\
= &
n^2
\sum_{i=1}^{n}
i \left \lfloor \frac{n}{i} \right \rfloor
\
& \sum_{i=1}^{n} ( n \ mod \ i \cdot \ m \ mod \ i)
\
= &
\sum_{i=1}^{n}
\left( n - i \left \lfloor \frac{n}{i} \right \rfloor \right) \left( m - i \left \lfloor \frac{m}{i} \right \rfloor \right)
\
= &
n^2m
+
\sum_{i=1}^{n}
i^2 \left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{m}{i} \right \rfloor
n\sum_{i=1}^{n}
i \left \lfloor \frac{m}{i} \right \rfloor
m\sum_{i=1}^{n}
i \left \lfloor \frac{n}{i} \right \rfloor
\
\end{align}
## 题解
于是分块大法好...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mo=19940417;
ll cal(int n, ll a) {
ll ret=a%mo*n%mo, tp=0;
for(int i=1, pos=0; i<=n; i=pos+1) {
pos=n/(n/i);
tp+=(a/i)%mo*(((ll)(pos+1)*pos/2-(ll)(i-1)*i/2)%mo)%mo;
if(tp>=mo) {
tp-=mo;
}
}
return (ret-tp+mo)%mo;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
if(n>m) {
swap(n, m);
}
printf("%lld\n", (cal(n, n)*cal(m, m)%mo-cal(n, (ll)n*m)+mo)%mo);
return 0;
}\]
最新文章
- 『.NET Core CLI工具文档』（十一）dotnet-test
- MySQL 清空慢查询文件
- AOE网的关键路径的计算
- HTML5 标签audio添加网页背景音乐代码
- javascript --- 事件冒泡与事件捕获
- Mac显示隐藏文件的终端命令
- [转]MongoDB for Java】Java操作MongoDB
- POJ 2240 && ZOJ 1082 Arbitrage 最短路,c++ stl pass g++ tle 难度:0
- CentOS配置java运行环境
- html-----005
- SQL中存储过程中使用事务,并且加入异常处理机制.
- Codeforces Round #257 (Div. 2) B Jzzhu and Sequences
- 站点系统压力測试Jmeter+Badboy
- C语言之printf函数
- char*赋值在常量区，不可以修改
- WKWebKit基础
- Python查看MQ队列深度
- phalcon——HTTP 请求
- python全栈开发-常用模块的一些应用
- linux 安装 ftp 实现文件共享