题目大意

数字n的分区是所有数字之和等于n的集合。 如果分区满足以下条件，则称为神秘分区：

  • 是整数，对于，。

  • 对于任意图片说明，图片说明

  • 图片说明
    设为的神秘分区的个数。现对于给出的每对，求出。

    解题思路

    感谢大佬的思路：https://blog.csdn.net/tianyizhicheng/article/details/107773762

  • 显而易见，这道题的做法必须为预处理每个数合法的构造数。
    由于这个构造的首尾差最大为2，所以我们可以把每个构造的都可以分成3段。现在我们设第一段数值为，那么第二段是，第三段是，设每段长度为。
    所以我们得到这样的式子：
    合并+替换：
    最后可以得到：

  • 引用一段对于差分的解释：
    图片说明

    https://blog.csdn.net/zhangchizc/article/details/107784622

  • 我们以时的情况为例，简单地打个表：
    图片说明

  • 所以，我们只用在对应位置上加减，还原为原序列即为f(n)。
    就像上面说的，我们预处理出f(n)的前缀和，查询时无脑输出即可。

    AC代码

    #include<bits/stdc++.h>
using namespace std;
const int N=3e5+10,M=1e5;
long long a[N],b[N],c[N];
int main()
{
  int T,l,r,x,i,j;
  for(i=3;i<=M;i++)
      for(j=1;i*j<=M;j++)
          x=i*j,a[x+3]++,a[x+i*2-1]--,b[x+i+1]++,b[x+i*2-1]--;
  //a[x+i-1+i-2+2]--,b[x+i-1+1+1]++,b[x+i-1+i-2+2]--;
  for(i=3;i<=M;i++) a[i]+=a[i-2],b[i]+=b[i-1];
  for(i=3;i<=M;i++) a[i]+=a[i-1]-b[i],c[i]=c[i-1]+a[i];
  scanf("%d",&T);
  for(i=1;i<=T;i++)
  {
      scanf("%d%d",&l,&r);
      printf("Case #%d: %lld\n",i,c[r]-c[l-1]);
  }
  return 0;
}