digit

This problem is as simple as short. Just find how many numbers from A to B with sum of digits from X to Y are divisible by K.

Input 
The first line contains 5 space-separated positive integers: A, B, X, Y, K

Output 
Output one number - answer for the question.

Constraints 
 0 < A, B, K  ≤ 10^13
 0 < X, Y  ≤ 1000
A ≤ B 
 0 < A, B,  ≤ 10^7 in 32 % of the test data

SAMPLE INPUT
5 86 1 6 4

SAMPLE OUTPUT
6

Explanation

There are 6 such numbers: 12, 20, 24, 32, 40, 60

Source: hackerearth | Difficulty: HARD
Tags: Number theory

Combinatorics

Dynamic programming

Complete search


Solutions:
A, B, X, Y, K=list(map(int,input().split()))

def digsum(x):
	r=0
	while x>0:
		r+=x%10
		x/=10
	return r	
	#return sum(map(int,str(x)))

def simpleCount(l,r):
	if r<=l: return 0
	cnt=0
	incr=0
	if l%K: incr=K-l%K
	
	for x in range(l+incr,r,K):
		s=digsum(x)
		if X<=s<=Y:cnt+=1
	return cnt
if K>1.e5 or B-A<=2000000:
	print(simpleCount(A,B+1))	
	exit()

FAC=1000000
maxDIGSUM=6*9+1
B+=1

mods=[[0]*K for i in range(maxDIGSUM)]
for i in range(FAC):
	mods[digsum(i)][i%K]+=1

for i in range(1,maxDIGSUM):
	for j in range(K):
		mods[i][j]+=mods[i-1][j]
	
res=0
last =A-(A%FAC)+FAC;
#assert last%FAC==0
res=simpleCount(A,last)
first=B-(B %FAC)
res+=simpleCount(first,B)
#assert first%FAC==0
#assert A<=last 
#assert last<first
#assert first<=B
#print A/FAC,last/FAC,first/FAC,B/FAC
su=digsum(last)-1
i=(last/FAC)%10
for x in range(last,first,FAC):
	m=x%K
	if m==0: m=K
	if i%10:
		su=su+1
	else:
		if i%100:
			su=su-8
		else:	
			if i%10000:
				if i%1000:
					su=su-17
				else: 
					su=su-26
			else:	
				su=digsum(x)
	i+=1
	if su<=Y:
		y=min(Y-su,maxDIGSUM-1)
		res+=mods[y][K-m]
	if su<=X-1:
		y=min(X-su-1,maxDIGSUM-1)
		res-=mods[y][K-m]
print(res)