自动搬运

查看原文

来自洛谷，原作者为

	Green_Hand **

搬运于2025-08-24 21:57:32，当前版本为作者最后更新于2018-12-22 15:15:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

此题做法：找规律

• 首先，我们需要分析什么样的数才能满足条件
• 我们通过一波打表就可以发现 $D_i=(i-1)\bmod9+1$
• 接着，我们可以发现满足下列条件之一就满足条件
  • $(x/2-1)\bmod9+1=2$
  • $(x/3-1)\bmod9+1=3$
  • $\dots\dots$
  • $(x/8-1)\bmod9+1=8$
  • $(x/9-1)\bmod9+1=9$
• 经过一系列简化，可得
  • $x\bmod9=1$
  • $x\bmod18=4$
  • $\dots\dots$
  • $x\bmod72=64$
  • $x\bmod81=0$
• 由于$22680 = lcm(9,18,27,36,45,54,63,72,81)$ 且$a \bmod b = (a + bc) \bmod b$
• 所以可得
  • $x\bmod9=(x+22680)\bmod9$
  • $x\bmod18=(x+22680)\bmod18$
  • $\dots\dots$
  • $x\bmod72=(x+22680)\bmod72$
  • $x\bmod81=(x+22680)\bmod81$
• 即如果用$bool$数组存该数是否满足条件，那么这个数组是循环的，且循环长度为$22680$
• 所以我们只需求出$1$到$22680$有哪些符合条件的数并维护前缀和即可
• 附代码

#include <cstdio>
#include <cstring>
using namespace std;

const int N = 22680;
typedef long long ll;
int T; ll l,r,sum[N + 10];

ll answer(ll x) { return sum[N] * (x / N) + sum[x % N]; }

int main()
{
	for(int i = 1,x;i <= N; ++ i)
		if((x = i * ((i - 1) % 9 + 1)) <= N) sum[x] = 1;
	for(int i = 2;i <= N; ++ i) sum[i] += sum[i - 1];
	for(scanf("%d",&T);T--;) scanf("%lld%lld",&l,&r),
		printf("%lld\n",answer(r) - answer(l - 1ll));
	return 0;
}