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

· · 个人记录

题意 ： 记 f(x)=\lfloor \lg x\rfloor ，即 x 在十进制下的位数。

给出 S ，求满足下列条件的数对 (l,r) 的个数 ：

答案对 10^9+7 取模。

------------ 这里有一个 $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})。

枚举 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}

也只需统计因数。

枚举 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)

细节真多……

#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;
}