组合数学 (习题): Mehta and the Typical Supermarket (HackerRank)

古城微笑少年丶 2022-02-15 01:49 573阅读 0赞

### Mehta and the Typical Supermarket ###

*  题目大意
 *  思路
 *  代码

# 题目大意 #

有  N N N 种硬币, 每种硬币无限个. 给定一个区间  \[ L , R \] \[L, R\] \[L,R\], 问里面有多少个数字可以由**这  N N N 种硬币中的某一种**组合出来. 也就是说问你区间内有多少个数可以被至少一枚硬币的面值整除

# 思路 #

典型的容斥原理, 比如有面值 2 和 3, 区间为  \[ 1 , 10 \] \[1, 10\] \[1,10\], 那么其中可以被组合出来的数有  \{ 2 , 3 , 4 , 6 , 8 , 9 , 10 \} \\\{2, 3, 4, 6, 8, 9, 10\\\} \{ 2,3,4,6,8,9,10\}, 很容易看出来, 如果一个数是这两个数的最小公倍数, 那么这个数应该被减掉 (系数为  − 1 -1 −1), 同理, 如果一个数是其中三个数的最小公倍数, 那么其系数应为  \+ 1 +1 \+1

# 代码 #

def gcd(a, b):
    	if b == 0:
    		return a
    	return gcd(b, a % b)
    
    def lcm(a, b):
    	return result = a * b // gcd(a, b)
    
    # 给定区间 L, R, 可以被 value 整除的数的个数
    def nPlan(value, L, R):
    	right = R // value
    	left = L // value
    	if L % value == 0:
    		left -= 1
    	return right - left
    
    def _solve(val, i, count, L, R):
    	if val > R:
    		return 0
    	if count == 0:
    		return nPlan(val, L, R)
    	result = 0
    	for j in range(i+1, N):
    		result += _solve(lcm(val, coins[j]), j, count-1, L, R)
    	return result
    	
    def solve(count, L, R):
    	result = 0
    	for i in range(N):
    		result += _solve(coins[i], i, count-1, L, R)
    	return result
    
    _N = int(input())
    N = 0
    coins = []
    
    for i in range(_N):
    	c = int(input())
    	# 如果某一个硬币的面值被另一个整除, 那么这个硬币就没用了
    	unique = True
    	for j in range(N):
    		if coins[j] % c == 0:
    			coins[j] = c
    			unique = False
    			break
    		if c % coins[j] == 0:
    			unique = False
    			break
    	if unique:
    		coins.append(c)
    		N += 1
    
    for _ in range(int(input())):
    	L, R = map(int, input().split())
    	result = 0
    	for i in range(1, N+1):
    		result += (-1)**(i-1) * solve(i, L, R)
    	print(result)