首先把【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; }