「BZOJ2405」数字
Description
.jpg)
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 补了个证明。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #define inf 1000000000 #define P 22680 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; ll a,b,s[P+1]; int D(int x) { int sum=0; while(x) { sum+=x%10; x/=10; } if(sum<10)return sum; return D(sum); } ll cal(ll x) { return x/P*s[P]+s[x%P]; } int main() { for(int i=1;i<=P;i++) if(D(i)*i<=P) s[D(i)*i]=1; for(int i=1;i<=P;i++) s[i]+=s[i-1]; T=read(); while(T--) { ll l=read(),r=read(); printf("%lld\n",cal(r)-cal(l-1)); } return 0; } |
计数器 9788252
OI 课件=>
OI 课件=>
楼下神犇啊！！！
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
对的，太强了！！！