E 算式子_牛客博客

E 算式子

数论题。

显然左半边右半边可以分开计算。

Update:修正了描述……之前写反了。

定义：

$\operatorname{cnt}(i)$ 为值 $\leq i$ 的元素的数量。

$\operatorname{ans}(i)$ 为 $x = i$ 时， $\sum \lfloor \dfrac{a_i}{x} \rfloor$ 的值。

考虑 $\lfloor \dfrac{a_i}{x} \rfloor$ 与 $\lfloor \dfrac{x}{a_i} \rfloor$ 如何计算。

对于 $\lfloor \dfrac{a_i}{x} \rfloor$ ，枚举每个 $x$ ，可以用整除分块的思想发现：

设 $\lfloor \dfrac{a_i}{x} \rfloor = k$ ，那么：

$l = k \times x,r = (k + 1) \times x - 1$ ，对于 $a_i \in [l,r]$ ，产生的贡献都为 $k$ 。

可以通过处理 $cnt$ 数组来计算该贡献。

对于 $\lfloor \dfrac{x}{a_i} \rfloor$ ，用类似的思想，考虑对被除数 $x$ 进行分块计算对每个 $x$ 值的贡献。

设 $\lfloor \dfrac{x}{a_i} \rfloor = k$ ，那么：

$l = k \times a_i,r = (k + 1) \times a_i - 1$ ，对于 $x \in [l,r]$ ，产生的贡献都为 $k$ 。

区间修改可以通过差分实现，最后做前缀和处理 $ans$ 数组。

如果枚举每个 $a_i$ 的话复杂度是不对的，例如全为 $1$ 的数组就可以卡掉。但可以借助 $cnt$ 数组，枚举值域进行计算，复杂度就正确了。

复杂度分析：不考虑 $n,m$ 的差异，复杂度为 $\sum _{i = 1}^n \lfloor \dfrac{n}{i} \rfloor$ ，可以证明是 $O(n \log n)$ 的，具体可以搜索调和级数。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
#define DEBUG
#define int long long
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize],*p1 = buf,*p2 = buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,bufSize,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    r=0;
    for(c = nc();!isdigit(c);) c = nc();
    for(;isdigit(c);c=nc()) r = r * 10 + c - 48;
    return r;
}
const int maxn = 2e6 + 100;
int n,m;
int a[maxn];
int cnt[maxn<<1],ans[maxn<<1];
signed main()
{
    read(n),read(m);
    for(int i = 1;i<=n;++i) read(a[i]),cnt[a[i]]++;

    for(int i = 1;i <= m; i++) if(cnt[i])
        for (int k = 1; i * k <= m; ++k)
        {
            int l = k * i, r = (k + 1) * i - 1;
            ans[l] += cnt[i] * k, ans[r + 1] -= cnt[i] * k;
        }
    for (int i = 1; i <= 2 * m; ++i) cnt[i] += cnt[i - 1];
    for (int i = 1; i <= 2 * m; ++i) ans[i] += ans[i - 1];
    long long last = 0;
    for(int i = 1;i<=m;++i)
    {
        long long sum = 0;
        /* 
        for (int l = 1, r, k; l <= i; l = r + 1)
        {
            k = i / l, r = i / k;
            sum += k * (cnt[r] - cnt[l - 1]);
        }
        */
        sum += ans[i];
        for (int k = 1; i * k <= m; ++k)
        {
            int l = k * i, r = (k + 1) * i - 1;
            sum += k * (cnt[r] - cnt[l - 1]);
        }

        last ^= sum;
    }
    printf("%lld\n",last);
    return 0;
}