ACM模版

描述


题解

这是一道十分有意思的问题，刚拿到手时第一感觉就是找周期性，可是总感觉缺点啥，不知道怎么去实现，然后看到了郑大的学长方寸的代码，顿悟，真是一个十分巧妙的处理手法。

首先，我们知道，这个序列中并不是所有的a[i]都对最后的结果能产生贡献，所以第一我们要删选出来能产生贡献的序列，这个序列a_[]一定是递减的，然后我们从最小的开始枚举构造周期性，不断用较大的a_[]来修正周期性，直到最后得到一个周期性数组vis[]，这里true代表一个周期结束，要重新开始周期，周期的开始始终是vis[1]，false代表渐变，对应的f[i]=f[i-1]+1，这里需要注意的是vis[]是一个严格的周期性数组，而f[]虽然存在周期性，却不是严格的，因为f[]的第一个周期的开始是val（代码中已给出），而剩下的周期的起点则是0。

总而言之，思路很好，代码实现起来不是太容易想，Orz~~~

代码

#include <iostream>
#include <cstdio>
#include <cstring>

#define ll long long

using namespace std;

const int MAXN = 2000;
const int MAXA = 100000;

ll mlop;
ll a[MAXN];
ll a_[MAXN];
ll f[MAXA];
ll sum[MAXA];
bool vis[MAXA];
int cnt;
int N, Q;

void init()
{
    memset(sum, 0, sizeof(sum));
    memset(vis, 0, sizeof(vis));

    cnt = 1;
    mlop = MAXA + 1;
    a_[0] = mlop;

    // 获取产生贡献的a[i]存入a_[j]
    for (int i = 0; i < N; i++)
    {
        if (mlop > a[i])
        {
            a_[cnt++] = a[i];
            mlop = a[i];
        }
    }

    mlop = a_[cnt - 1];
    for (int i = cnt - 2; i >= 0; i--)
    {
        ll j;
        vis[mlop] = true;

        // 周期性，ture表示返回周期开始，false表示渐变（上一个+1）
        // 周期始终从vis[1]开始
        for (j = mlop + 1; j + mlop - 1 <= a_[i]; j += mlop)
        {
            memcpy(&vis[j], &vis[1], sizeof(bool) * mlop);
        }
        if (j < a_[i])
        {
            memcpy(&vis[j], &vis[1], sizeof(bool) * (a_[i] - j + 1));
        }
        mlop = a_[i];
    }

    ll val = 1;

    // 获取周期起点值
    for (int i = 1; i < cnt; i++)
    {
        val %= a_[i];
    }

    f[1] = val;
    sum[1] = f[1];
    for (int i = 2; i <= MAXA; i++)
    {
        f[i] = f[i - 1] + 1;
        if (vis[i])
        {
            f[i] = 0;
        }

        sum[i] = sum[i - 1] + f[i];
    }
}


int main()
{
    int T;
    scanf("%d", &T);

    while (T--)
    {
        scanf("%d", &N);

        for (int i = 0; i < N; i++)
        {
            scanf("%lld", &a[i]);
        }

        init();
        scanf("%d", &Q);

        while (Q--)
        {
            ll l, r;
            scanf("%lld%lld", &l, &r);
            printf("%lld\n", sum[r] - sum[l - 1]);
        }
    }

    return 0;
}