题解 P4193 【数字】

Green_Hand · 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;
}