当前位置： 移动技术网 > IT编程>开发语言>C/C++ > BZOJ2956: 模积和(数论分块)

BZOJ2956: 模积和(数论分块)

2019年02月08日  | 移动技术网IT编程  | 我要评论

王长喜官网,qisuu,句芒是谁的后裔

题意

题目链接

sol

啊啊这题好恶心啊，推的时候一堆细节qwq

\(a \% i = a - \frac{a}{i} * i\)

把所有的都展开，直接分块。关键是那个\(i \not= j\)的地方需要减。。。。

然后就慢慢写就好了

#include<bits/stdc++.h>
#define pair pair<int, int>
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define int long long
#define ll long long
#define fin(x) {freopen(#x".in","r",stdin);}
#define fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int maxn = 1e6 + 10, mod = 19940417, inf = 1e9 + 10;
const double eps = 1e-9;
template <typename a, typename b> inline ll add(a x, b y) {
    if(x + y < 0) return x + y + mod;
    return x + y >= mod ? x + y - mod : x + y;
}
template <typename a, typename b> inline void add2(a &x, b y) {
    if(x + y < 0) x = x + y + mod;
    else x = (x + y >= mod ? x + y - mod : x + y);
}
template <typename a, typename b> inline ll mul(a x, b y) {
    x = (x + mod) % mod;
    y = (y + mod) % mod;
    return 1ll * x * y % mod;
}
template <typename a> inline ll sqr(a x) {
    return 1ll * x * x;
}
int n, m, a, b;
int sum(int l, int r) {
    if(l == r) return l;
    int n = r - l + 1;
    if(n & 1) return add(mul(l, n), mul(n, (n - 1) / 2));
    else return add(mul(l, n), mul(n / 2, n - 1));
}
int calc(int n) {
    int ret = 0;
    for(int i = 1, j; i <= n; i = j + 1) {
        j = n / (n / i);
        add2(ret, mul(n / j, sum(i, j)));
    }
    return ret;
}
int get(int x) {
    int a = x, b = 2 * x + 1, c = x + 1;
    if(a % 2 == 0) a /= 2;
    else if(b % 2 == 0) b /= 2;
    else if(c % 2 == 0) c /= 2;
    if(a % 3 == 0) a /= 3;
    else if(b % 3 == 0) b /= 3;
    else if(c % 3 == 0) c /= 3;
    return mul(mul(a, b), c);
}
int fuck2(int i, int j) {//sum k^2
    return add(get(j), -get(i - 1));
}
int calc2() {
    int ret = 0;
    for(int i = 1, j; i <= n; i = j + 1) {
        j = min(m / (m / i), n / (n / i));
        int a = m / i, b = n / i;
        add2(ret, add(add(mul(n, mul(a, sum(i, j))), mul(m, mul(b, sum(i, j)))), -mul(mul(a, b), fuck2(i, j))));
    }
    return ret;
}
signed main() {
    cin >> n >> m;
    if(n > m) swap(n, m);
    a = calc(n);
    b = calc(m);
    int ans = mul(add(mul(n, n), -a), add(mul(m, m), -b));
    add2(ans, -mul(n, mul(n, m)));
    add2(ans, calc2());
    cout << ans;
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网