E 算式子

E 算式子

数论题。

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

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

定义：

为值 的元素的数量。

为 时， 的值。

考虑 与 如何计算。

对于 ，枚举每个 ，可以用整除分块的思想发现：

设 ，那么：

，对于 ，产生的贡献都为 。

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

对于 ，用类似的思想，考虑对被除数 进行分块计算对每个 值的贡献。

设 ，那么：

，对于 ，产生的贡献都为 。

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

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

复杂度分析：不考虑 的差异，复杂度为 ，可以证明是 的，具体可以搜索调和级数。

#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;
}