AtCoder Regular Contest 090 - Number of Digits

For a positive integer n, let us define f(n) as the number of digits in base 10.
You are given an integer S.
Count the number of the pairs of positive integers (l, r) (l \leq r) such that f(l) + f(l + 1) + ... + f(r) = S, and find the count modulo 10^9 + 7.

-----Constraints-----
 - 1 \leq S \leq 10^8

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the answer.

-----Sample Input-----
1

-----Sample Output-----
9

There are nine pairs (l, r) that satisfies the condition: (1, 1), (2, 2), ..., (9, 9).

Source: atcoder | Difficulty: VERY_HARD


Solutions:
import math
import random

class Prime:
	seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

	def is_prime(self, n):
		is_prime_common = self.is_prime_common(n)
		if is_prime_common is not None:
			return is_prime_common
		if n < 2000000:
			return self.is_prime_bf(n)
		else:
			return self.is_prime_mr(n)

	def is_prime_common(self, n):
		if n == 1:
			return False
		if n in Prime.seed_primes:
			return True
		if any(map(lambda x: n % x == 0, self.seed_primes)):
			return False

	def is_prime_bf(self, n):
		for k in range(2, int(math.sqrt(n)) + 1):
			if n % k == 0:
				return False
		return True

	def is_prime_mr(self, n):
		d = n - 1
		while d % 2 == 0:
			d //= 2
		witnesses = self.get_witnesses(n)
		for w in witnesses:
			t = d
			y = pow(w, t, n)
			while t != n - 1 and y != 1 and (y != n - 1):
				y = y ** 2 % n
				t *= 2
			if y != n - 1 and t % 2 == 0:
				return False
		return True

	def get_witnesses(self, num):

		def _get_range(num):
			if num < 2047:
				return 1
			if num < 1373653:
				return 2
			if num < 25326001:
				return 3
			if num < 3215031751:
				return 4
			if num < 2152302898747:
				return 5
			if num < 3474749660383:
				return 6
			if num < 341550071728321:
				return 7
			if num < 38255123056546413051:
				return 9
			return 12
		return self.seed_primes[:_get_range(num)]

	def gcd(self, a, b):
		if a < b:
			(a, b) = (b, a)
		if b == 0:
			return a
		while b:
			(a, b) = (b, a % b)
		return a

	@staticmethod
	def f(x, n, seed):
		p = Prime.seed_primes[seed % len(Prime.seed_primes)]
		return (p * x + seed) % n

	def find_factor(self, n, seed=1):
		if self.is_prime(n):
			return n
		(x, y, d) = (2, 2, 1)
		count = 0
		while d == 1:
			count += 1
			x = self.f(x, n, seed)
			y = self.f(self.f(y, n, seed), n, seed)
			d = self.gcd(abs(x - y), n)
		if d == n:
			return self.find_factor(n, seed + 1)
		return self.find_factor(d)

	def find_factors(self, n):
		primes = {}
		if self.is_prime(n):
			primes[n] = 1
			return primes
		while n > 1:
			factor = self.find_factor(n)
			primes.setdefault(factor, 0)
			primes[factor] += 1
			n //= factor
		return primes

def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while 0 < b:
		(a, b) = (b, a % b)
	return a

def powmod(a, x, m):
	y = 1
	while 0 < x:
		if x % 2 == 1:
			y *= a
			y %= m
		x //= 2
		a = a ** 2
		a %= M
	return y
M = 10 ** 9 + 7
prime = Prime()

def solve(s):
	if s == 1:
		return 9
	ans = 0
	n = 1
	c = 9
	while n * c < s:
		n += 1
		c *= 10
	ans += s // n
	for log_r in range(n - 1, n + 1):
		c_r = 9 * 10 ** (log_r - 1)
		sum_r = log_r * c_r
		for log_l in range(1, log_r):
			mid_f = 0
			for i in range(log_l + 1, log_r):
				mid_f += i * 9 * 10 ** (i - 1)
			if s <= mid_f:
				continue
			res = s - mid_f
			c_l = 9 * 10 ** (log_l - 1)
			if log_l * c_l + sum_r < res:
				continue
			g = gcd(log_r, log_l)
			if res % g != 0:
				continue
			c_l_max = min(c_l, (res - 1) // log_l)
			while 0 < c_l_max:
				if (res - log_l * c_l_max) % log_r == 0:
					break
				c_l_max -= 1
			if c_l_max == 0:
				continue
			c_l_min = 1
			if sum_r < res:
				c_l_min = (res - sum_r + log_l - 1) // log_l
			div = log_r // g
			ans += (c_l_max - c_l_min + div) // div
	factors = prime.find_factors(s)
	num_prime_factors = len(factors)
	prime_factors = []
	count_limit = []
	count = [0] * num_prime_factors
	for k in factors.keys():
		prime_factors.append(k)
		count_limit.append(factors[k])
	loop = True
	while loop:
		p = 1
		for (i, f) in enumerate(prime_factors):
			p *= f ** count[i]
		if n <= p:
			ans += 9 * powmod(10, p - 1, M)
			ans += M - s // p
			ans %= M
		count[0] += 1
		for (i, limit) in enumerate(count_limit):
			if limit < count[i]:
				if i == num_prime_factors - 1:
					loop = False
					break
				count[i + 1] += 1
				count[i] = 0
	return ans

def main():
	s = int(input())
	print(solve(s))
main()


s = int(input())
dv = []
mod = 10 ** 9 + 7
for i in range(1, int((s + 0.5) ** 0.5) + 1):
	if s % i == 0:
		if s // i != i:
			dv.append(s // i)
		dv.append(i)
dv.sort()
ans = 0
cnt = 0
for i in dv:
	if s // i <= 8:
		break
	ans += pow(10, s // i - 1, mod) * 9 - i
	ans %= mod
	cnt += 1
ans += (s - 1) // 8
t = s
for i in range(1, 11):
	minus = i * 9 * 10 ** (i - 1)
	if minus > t:
		mx = (t + i - 1) // i + 10 ** (i - 1)
		break
	else:
		t -= minus
bettable = [[[0, 0] for i in range(9)] for j in range(9)]
for i in range(9):
	for j in range(i + 1, 9):
		for k in range(i + 1, j):
			bettable[i][j][0] += k * 10 ** (k - 1) * 9
			bettable[i][j][1] += 10 ** (k - 1) * 9
for i in range((s + 7) // 8, mx):
	avgl = s // i
	if avgl * i == s and 10 ** (avgl - 1) * 9 >= i:
		ans += 10 ** (avgl - 1) * 9 - i + 1
		continue
	avgh = avgl + 1
	for l in range(1, avgl + 1):
		for h in range(avgh, 9):
			t = s - bettable[l][h][0]
			j = i - bettable[l][h][1]
			if t < 0 or j < 0:
				continue
			lnum = min(j, 10 ** (l - 1) * 9)
			hnum = min(j, 10 ** (h - 1) * 9)
			if (h * j - t) % (h - l) == 0:
				x = (h * j - t) // (h - l)
				if 0 < x <= lnum and 0 < j - x <= hnum:
					ans += 1
					break
print(ans % mod)


import sys
input = sys.stdin.readline
from fractions import gcd
import numpy as np
MOD = 10 ** 9 + 7
S = int(input())
M = 10 ** 4

def type_1(S):
	cnt = 0
	n = np.arange(1, M + 1)
	k_max = (S - 1) // n
	k_min = np.maximum(M + 1, S // n)
	cnt += np.maximum(0, k_max - k_min + 1).sum()
	k = np.arange(9, M + 1)
	n_max = (S - 1) // k
	n_min = S // (k + 1) + 1
	cnt += np.maximum(0, n_max - n_min + 1).sum()
	return cnt
type_1(S)

def type_2(S):
	cnt = 0
	div = np.arange(1, M + 1, dtype=np.int64)
	div = set(div[S % div == 0])
	div |= set((S // x for x in div))
	for d in div:
		n = S // d
		if d < 10:
			total = 9 * 10 ** (d - 1)
			cnt += max(0, total - n + 1)
		else:
			total = 9 * pow(10, int(d) - 1, MOD)
			cnt += total - n + 1
	return cnt % MOD

def type_3(S):
	cnt = 0
	for R in range(1, 10):
		for L in range(1, R):
			mid = sum((i * 9 * 10 ** (i - 1) for i in range(L + 1, R)))
			rest = S - (L + mid + R)
			if rest < 0:
				continue
			x_max = 9 * 10 ** (L - 1) - 1
			y_max = 9 * 10 ** (R - 1) - 1
			g = gcd(L, R)
			if rest % g != 0:
				continue
			L0 = L // g
			R0 = R // g
			rest //= g
			for x0 in range(R0):
				if (L0 * x0 - rest) % R0 == 0:
					break
			y0 = (rest - L0 * x0) // R0
			t_min = 0
			t_max = (x_max - x0) // R0
			t_max = min(t_max, y0 // L0)
			t_min = max(t_min, (y0 - y_max + L - 1) // L0)
			cnt += max(0, t_max - t_min + 1)
	return cnt
answer = (type_1(S) + type_2(S) + type_3(S)) % MOD
print(answer)