[数论记录]AT3884 [ARC090D] Number of Digits

**题意** ： 记 $f(x)=\lfloor \lg x\rfloor$ ，即 $x$ 在十进制下的位数。 给出 $S$ ，求满足下列条件的数对 $(l,r)$ 的个数 ： - $1\leq l\leq r$ - $\sum\limits_{i=l}^rf(i)=S$ 答案对 $10^9+7$ 取模。 $S\leq 10^8$ ，时限$\texttt{2s}$。 ------------ 这里有一个 $S\leq 10^{10}$ 且 $50$ 组数据的加强版 : [Link](https://www.luogu.com.cn/problem/U150370) 由于 $f$ 是单调递增的上凸函数，在合法方案中，当 $f(l)$ 增大时， $f(r)-f(l)$ 减小。 - **Case 1** : $f(r)-f(l)=0$ 枚举 $f$ 的值。$f(x)=k$ 的 $x$ 的数目为 $9\times 10^{k-1}$。 若 $k$ 是 $S$ 的因数，则选取一个长为 $|S|/k$ 的区间即可满足题意。 故方案数为 ： $$\sum\limits_{k|S}\max\Big\{9\times 10^{k-1}-|S|/k+1\ ,0\Big\}$$ 大力求因数，复杂度为 $O(\sqrt{S})$。 - **Case 2** : $f(r)-f(l)=1$ 枚举 $f(l)=k$。设区间中 $f(x)=k$ 的有 $a$ 个，$f(x)=k+1$ 的有 $b$ 个。 为了与 Case 1 区分，这里要求 $a,b>0$ 。且由于个数限制也有 $a\leq 9\times 10^{k-1},\ b\leq 9\times 10^k$。 化式子 ： $$ \begin{aligned} S&=a*k+b*(k+1)\\ &=(a+b)k+b\\ b&=S-(a+b)k \end{aligned} $$ 注意到当确定 $a+b$ 之后就能确定 $a,b$ ，故只需计数合法的 $a+b$ 的个数。 由 $0<b<a+b$ ，可得 $0<S-(a+b)k<a+b$ 。 解得 $\big\lfloor\tfrac{S}{k+1}\big\rfloor+1\leq (a+b)\leq \big\lfloor\tfrac{S-1}{k}\big\rfloor$。 还要考虑 $a,b$ 的上界，将上界代入并用得到的 $a+b$ 修正上述范围。 注意到当 $k>\lg S$ 时，这两个条件必定能满足，所以只有很小一部分 $k$ 需要修正。 其他的部分为 $$ \begin{aligned} &\sum\limits_{k\geq lim}\big\lfloor\tfrac{S-1}{k}\big\rfloor-\big\lfloor\tfrac{S}{k+1}\big\rfloor\\ =&\lfloor\tfrac{S}{lim}\big\rfloor+\sum\limits_{k\geq lim}\big\lfloor\tfrac{S-1}{k}\big\rfloor-\big\lfloor\tfrac{S}{k}\big\rfloor\\ =&\lfloor\tfrac{S}{lim}\big\rfloor-\sum\limits_{k\geq lim}[k|S]\\ \end{aligned} $$ 也只需统计因数。 - **Case 3** : $f(r)-f(l)>1$ 枚举 $f(r)-f(l)=c$ ，枚举 $f(l)=k$ ，则 $f(r)=k+c$。 由于此时我们跨越了至少一整段，$k,c$ 的范围都是 $O(\lg S)$ ，枚举量是很小的。 设区间中 $f(x)=k$ 的有 $a$ 个，$f(x)=k+c$ 的有 $b$ 个。 此时仍然有 $0<a\leq 9\times 10^{k-1},\ 0<b\leq 9\times 10^{k+c-1}$。 计算出中间整段的 $f$ 的和 $M$ ，记 $S'=S-M$。则有 $S'=ak+b(k+c)$ 。 问题转化为 ： 给出不定方程 $c=ax+by$ ，求解 $x,y$ （在一定范围内）的对数。 记 $d=\gcd(a,b)$ ，若 $d\!\not|\ c$ ，则无解。否则将 $c,a,b$ 除以 $d$ 转化为 $a\perp b$ 的情况。 用 $\rm EXgcd$ 得到特解 $x_*,y_*$ （注意可能无解），则通解为 $\begin{cases}x=x_*+kb\\y=y_*-ka\end{cases}$ 将范围不等式的四个边界分别代入，即可得知方案数。 这部分的复杂度为 $O\big({\rm poly}(\log S)\big)$ 细节真多…… ```cpp #include<algorithm> #include<cstdio> #define ll long long using namespace std; const int mod=1000000007; ll powM(ll a,ll t){ ll ret=1;t%=(mod-1); while(t){ if (t&1)ret=ret*a%mod; a=a*a%mod;t>>=1; }return ret; } void exgcd(ll a,ll b,ll &x,ll &y){ if (b==0){x=1;y=0;return ;} exgcd(b,a%b,y,x);y-=(a/b)*x; } int gcd(int a,int b) {return !b ? a : gcd(b,a%b);} ll n,lim[15]; int main() { scanf("%lld",&n); lim[1]=9;for (int i=2;i<=13;i++)lim[i]=lim[i-1]*10; ll ans=0; for (int i=1;1ll*i*i<=n;i++) if (n%i==0){ ll d=i; if (d>12)ans--; if (d>12||n/d<=lim[d]) ans=(ans+9*powM(10,d-1)-n/d+1)%mod; if (1ll*i*i==n)continue; d=n/i; if (d>12)ans--; if (d>12||n/d<=lim[d]) ans=(ans+9*powM(10,d-1)-n/d+1)%mod; } for (int k=1;k<=12;k++){ ll l=max(n/(k+1)+1,(n-lim[k+1]*(k+1)+k-1)/k+lim[k+1]) ,r=min((n-1)/k,(n-lim[k]*k)/(k+1)+lim[k]); ans=(ans+((r>=l) ? r-l+1 : 0))%mod; }ans=(ans+n/13)%mod; for (int kl=1;kl<=12;kl++) for (int kr=kl+2;kr<=12;kr++){ ll s=n; for (int j=kl+1;j<kr;j++)s-=lim[j]*j; int d=gcd(kl,kr); if (s%d||s<=0)continue; s/=d;int a=kl/d,b=kr/d; ll limx=lim[kl],limy=lim[kr],x,y,xl,xr; exgcd(a,b,x,y);x*=s;y*=s; x=(x%b+b)%b;xl=!x ? b : x; y=(y%a+a)%a;if (!y)y=a;xr=(s-b*y)/a; x+=limx/b*b+b;while (x>limx)x-=b;xr=min(xr,x); y+=limy/a*a+a;while (y>limy)y-=a;xl=max(xl,(s-b*y)/a); if (xl<=xr)ans+=(xr-xl)/b+1; } printf("%lld",(ans+mod)%mod); return 0; } ```