给定两个整数 n,m ,请你计算有多少个整数二元组 (x,y) 能够同时满足以下所有条件: 1≤x≤n 1≤y≤m (x+y)mod5=0 注意,(1,2) 和 (2,1) 视为两个不同二元组。C++代码1≤n,m≤1e6
时间: 2023-12-11 13:04:55 浏览: 118
好的,根据你的要求,我来为你提供一份 C++ 代码实现,它可以处理 1≤n,m≤1e6 的情况:
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
int n, m;
LL c[N];
inline int lowbit(int x) {
return x & -x;
}
void add(int x, int v) {
for (int i = x; i <= n; i += lowbit(i)) {
c[i] += v;
}
}
LL query(int x) {
LL res = 0;
for (int i = x; i; i -= lowbit(i)) {
res += c[i];
}
return res;
}
int main() {
scanf("%d%d", &n, &m);
LL ans = 0;
for (int i = 1; i <= n; i++) {
int t = (5 - (i % 5)) % 5;
ans += query(min(m, i + t)) - query(max(0, i - 5 + t - 1));
add(i + t, 1);
}
printf("%lld\n", ans);
return 0;
}
```
代码中,我们首先输入 n 和 m,然后用 c 数组来维护树状数组。对于每个 i,我们计算出它与 5 的余数 t,然后查询满足条件的 y 的范围 [max(0, i-5+t-1), min(m, i+t)],并将该范围内的位置在树状数组中的值都加 1。最后,将所有的答案累加起来,即为最终答案。
希望这份代码能够帮到你!
阅读全文