solution
首先利用前缀和思想,用的答案减去的答案就是的答案。
所以现在我们只需要考虑如何求出中每个数码在所有数字的约数中出现的次数即可。
然后是非常经典的将计算每个数字的约数改为枚举约数计算该约数的倍数有多少个。暴力做就是。这样复杂度是无法通过此题。
看到上面式子可以数论分块,所以直接套一个数论分块。
然后还有一个小问题就是数论分块如何求区间中x出现的次数。我的做法是先预处理一个10的整数幂,然后查看以x为最高位的每个大小的区间中是否有答案。统计一下。
总复杂度就是
code
/* * @Author: wxyww * @Date: 2020-04-06 09:59:24 * @Last Modified time: 2020-04-06 10:25:25 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } ll mi[10]; ll solve(int n,ll x) { ll ret = 0; for(ll l = 1,r;l <= n;l = r + 1) { r = n / (n / l); // printf("%d %d ",l,r); ll tmp = 0; for(int i = 0;i <= 9;++i) { tmp += max(0ll,min(r,(x + 1) * mi[i] - 1) - max(l,x * mi[i]) + 1); } // printf("%d\n",tmp); ret += (n / l) * tmp; } return ret; } int main() { int l = read(),r = read(); mi[0] = 1; for(int i = 1;i <= 9;++i) mi[i] = mi[i - 1] * 10; // cout<<solve(4,2)<<endl; for(int i = 1;i <= 9;++i) cout<<solve(r,i) - solve(l - 1,i)<<endl; return 0; }