ARC090F Number of Digits

,

Description

https://www.luogu.com.cn/problem/AT_arc090_d

Solution

根号做法，目前最优解。

记位数为 $x$ 的数的个数为 $g(x)=9\times 10^{x-1}$

显然要分类讨论 $f(l)$ 和 $f(r)$ 的关系。

  1. $f(l)=f(r)$：

    答案为 $g(l)-\dfrac{n}{f(l)}+1$，还需要满足 $f(l)|n$，可以通过枚举因数做到 $O(\sqrt n)$。因为因数个数不是瓶颈所以可以放心使用快速幂。

  2. $f(l)+1=f(r)$：

    考虑列方程 $x\times f(l)+y\times (f(l)+1)=k$ 且 $x,y>0$。

    化简后有 $\lfloor\dfrac{k}{f(l)}\rfloor <x+y\le \lfloor\dfrac{k-1}{f(l)}\rfloor$。对于 $f(l)\ge 8$ 的情况没有 $x,y$ 的限制，容易想到用整除分块去做。否则可以跟下面一种情况一起做。

  3. $f(l)+1<f(r)$：

    中间的数一定要取，根据 $n$ 的范围可以知道 $f(r)\le 8$。那么可以直接枚举 $f(l),f(r)$，然后求解二元一次方程即可。注意两个系数存在上下界。

最后的复杂度就是 $O(\sqrt n+\log ^3 n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int long long 
#define maxn
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
ll power(ll x,int y=mod-2,int p=mod) {
	ll sum=1;x%=p;
	while (y) {
		if (y&1) sum=sum*x%p;
		x=x*x%p;y>>=1;
	}
	return sum;
}
int gcd(int x,int y) {return !y?x:gcd(y,x%y);}
void exgcd(int a,int b,int &x,int &y) {
	if (!b) return x=1,y=0,void();
	else exgcd(b,a%b,y,x),y-=a/b*x;
}
int n,ans;
void add(int &x,int y) {x=(x+y)%mod;}
int F(int x) {
	return power(10,x-1)*9%mod;
}
void calc(int x) {
	int res=F(x);
	if (x<=8&&res*x<n) ;
	else add(ans,res-n/x+1);
}
signed main(void){
	int i,x,y,j;
	read(n);
	for (i=1;i*i<=n;i++) if ((n%i)==0) {
		calc(i);
		if (i*i<n) calc(n/i);
	} 
	int res=ans;
	for (i=1;i<=8;i++) {
		int res=0;
		for (j=i+1;j<=8;j++) {
			if (res+i+j>n) break;
			int tmp1=F(i)-1,tmp2=F(j)-1;
			int a=i,b=j,c=n-res-i-j,d=gcd(a,b);
			res+=F(j)*j;
			if (c%d) continue;
			exgcd(a,b,x,y);
			a/=d,b/=d,c/=d;
			x*=c,y*=c;
			int L=max(ceil(1.0*(-x)/b),ceil(1.0*(y-tmp2)/a));
			int R=min(floor(1.0*(y)/a),floor(1.0*(tmp1-x)/b));
			if (L<=R) ans+=R-L+1;
		}
	}
	
	int l,r;
	for (l=9;l<=n;l=r+1) {
		r=min(n,n/(n/l));
		add(ans,mod-(r-l+1)*(n/l)%mod);
	}
	for (l=8;l<n;l=r+1) {
		r=min(n-1,(n-1)/((n-1)/l));
		add(ans,(r-l+1)*((n-1)/l));
	}
	printf("%lld\n",ans%mod);
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i