首先把【L , R】的问题转化成【1 , R】-【1 , L-1】,因为想要求1 ~ n中有几个数约数有x,可以通过n/x求得;
然后对于每个数码1,2,3....分别求,以1为例:
求1 ~ n中约数数码为1的,应该要求这样的一些区间【1,1】、【10,19】、【100,199】【1000,1999】,以第二个区间【10,19】为例,就是要求n/10,n/11,.........,n/19,但是可以发现其实有很多求出来的值是相同,例如当n是24时,24/13,24/14,24/15,24/16......24/24的结果都是1,所以可以用整个结果相同的一个区间来算。怎么确定这个区间的边界,就是一个整除分块问题,开始的区间的左键为l,区间右键就为n/(n/l),这个区间的求出的结果都为n/l,这个区间的长度就是r-l+1;
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
ll L,R;
ll solve(ll x,ll d){
ll res = d/x;//先求1~d内约数有x的有几个
//x0~x9,x00~x99,.....
for(ll l = x*10,r = x*10+9;l <= d;l*=10,r=r*10+9){
ll k = min(r,d);//真正的上界
for(ll i = l;i <= k;){
ll mx = min((d/(d/i)),k);
res += (mx-i+1)*(d/i);
i = mx+1;
}
}
return res;
}
int main(){
scanf("%lld%lld",&L,&R);
for(ll i = 1;i <= 9;i++){
printf("%lld\n",solve(i,R) - solve(i,L-1));
}
return 0;
}
京公网安备 11010502036488号