JZOJ1938 BZOJ2154 Crash的数字表格

题目链接：BZOJ2154

思路

题目就是要你求

考虑到

式子变成：

很烦，我们先枚举它：

转换成的形式：

就是：

反演：



然后发现，后面两个其实是等差数列，可以求。前面的可以分块，后面的和也可以分块，复杂度就是线性筛法复杂度+分块，也就是
在线筛的过程中顺便求一下的前缀和，就可以随便搞了。

Code：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
inline int min(int a, int b) { return a < b ? a : b; }
 
typedef long long ll;
const int N = 1e7 + 7;
const ll P = 20101009;
 
int n, m, tot = 0, check[N], prime[N / 10], mu[N], sum[N];
ll ans = 0;
 
inline ll getsum(ll n) { return n * (n + 1) % P * 10050505LL % P; } //这个东西是2的逆元,别吓傻了
ll solve(int n, int m)
{
    ll ret = 0;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        ret = (ret + (sum[r] - sum[l - 1] + P) % P * getsum(n / l) % P * getsum(m / l) % P) % P;
    }
    return ret;
}
 
int main()
{
    scanf("%d%d", &n, &m);
    if (n > m) n ^= m ^= n ^= m;
    mu[1] = sum[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!check[i]) prime[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot; j++)
        {
            if (prime[j] * i > n) break;
            check[prime[j] * i] = 1;
            if (i % prime[j]) mu[prime[j] * i] = -mu[i];
            else { mu[prime[j] * i] = 0; break; }
        }
    }
    for (int i = 2; i <= n; i++) sum[i] = (sum[i - 1] + mu[i] * i % P * i % P) % P;
    for (int g = 1, r; g <= n; g = r + 1)
    {
        r = min(n / (n / g), m / (m / g));
        ans = (ans + (r - g + 1LL) * (r + g) % P * 10050505LL % P * solve(n / g, m / g) % P) % P;
    }
    printf("%lld\n", ans);
    return 0;
}