【bzoj2405】数字

2014年12月24日1,3213

Description

Input

第一行一个整数T,表示数据组数。

以下每一行两个数L、R(保证区间合法),代表询问[L, R]。

Output

输出T行,每行一个数,表示在这个区间内小D喜欢的数出现了多少次。

你的输出当且仅当和标准输出一样才能得该测试点满分。

Sample Input

3
1 5
3 9
8 8

Sample Output

2
2
0

HINT

L,R<=10^18,T<=20

题解

显然D(x)=D(x+9)

观察下列式子

1 * D(1) = 1

10 * D(10) = 10

19 * D(19) = 19

即被1*9除余1的数都被喜欢

2 * D(2) = 4

11 * D(11) = 22

20 * D(20) = 40

即被2*9取余为4的都被喜欢

被k*9取余为k^2的都满足(1<=k<=9)

显然其它情况是不被喜欢的

lcm(1~9) * 9 =22680

即x与x+22680在mod k*9 意义下同余(1<=k<=9)

则x与x+22680只能同时被喜欢或不被喜欢

所以s[x]=x/22680*s[22680]+s[x mod 22680]

11.27 *1

12.24 补了个证明。。。

 

  • 2015年11月26日 下午4:47 回复

    ans(1~n)= (n+18)/27 + n/81 + (n+8)/9 + (n+14)/18 + (n+14)/63 – (n+14)/126 + (n+20)/36 + (n+20)/45 – (n+20)/180

    #1  
    • cgt2015年12月2日 下午9:17 回复

      对的,太强了!!!

      #11
  • cgt2015年12月2日 下午9:17 回复

    楼下神犇啊!!!

    #2