每日一题-数码

数码
首先显然转化成[1,l-1]和[1,r]分别算
对于一个数
假设最高位为d
那么可以写成\(d\times {10}^k+x,x<{10}^k\)
设t满足
\(t(d\times {10}^k+x)<=R\)
那么这个数的贡献就是 \(\frac {R}{d\times {10}^k+x}\)下取整，那么每次固定k，d，分块算即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
using namespace std;
typedef long long ll;
const int N=1e6+5;
int l,r;
ll b[20];
ll a[20];
void solve(int x){
	ll i,j,t;
	fo(d,1,9){
		fo(k,0,10){
			if (d*b[k]>x) break;
			i=0;
			while (i<b[k]){
				t=x/(d*b[k]+i);
				if (!t) break;
				j=min(d*b[k]+b[k]-1,x/t)-d*b[k];
				
				a[d]+=t*(j-i+1);
				i=j+1;
			}
		}
	}
}
int main(){
//	freopen("data.in","r",stdin);
	b[0]=1;
	fo(i,1,10) {
		b[i]=b[i-1]*10;
	}
	scanf("%d %d",&l,&r);
	
	solve(l-1);
	fo(i,1,9) a[i]=-a[i];


	solve(r);
	fo(i,1,9) printf("%lld\n",a[i]);
	return 0;
}

自从写了物理实验报告后，latax越来越熟练了