大意:
数字n的分区是所有数字之和等于n的集合。 如果分区 满足以下条件,则称为神秘分区:
是整数,对于 ,。
对于任意 , 。
。
令f(n)为n的神秘分区的数量。给定l和r,请计算。
输入描述:
自己看原题。
输出描述:
对于每个测试用例,以“ Case #x:y”形式输出一行,其中x是测试用例编号,y是答案。
思路:
- 数n的拆分,需要满足最大和最小差2,相邻两个数差不能超过1
-f(n)表示拆分的个数,给定l,r求区间和
拆分肯定由三种连续的数构成,比如l,l+1,l+2
可以通过枚举l去初始化f(i);
代码:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; ll cnt[maxn*5]; int main(){ freopen("azw.txt","r",stdin); memset(cnt,0,sizeof(cnt)); for (int i=3;i<=maxn;i++) for (int j=1;i*j<=maxn;j++){ cnt[i*j+3]++; cnt[i*j+i+1]--; cnt[i*j+i+2]--; cnt[i*(2+j)]++; } for (int i=3;i<=maxn;i++) cnt[i]+=cnt[i-1]; for (int i=3;i<=maxn;i++) cnt[i]+=cnt[i-2]; for (int i=3;i<=maxn;i++) cnt[i]+=cnt[i-1]; int T; scanf("%d",&T); for (int t=1;t<=T;t++){ int l,r; scanf("%d%d",&l,&r); printf("Case #%d: %lld\n",t,cnt[r]-cnt[l-1]); } return 0; }