考虑区间$[1,n]$，能被x整除的数量为$n/x$。

在包含偏序上使用抽屉原理反演，不难得到区间$[1,n]$中能被集合中任意一个元素整除的数的数量，用区间长度减去该值即为区间$[1,n]$不能被集合整除的数的数量。

最终结果为区间$[1,r]$不能被集合整除的数的数量减去区间$[1,l-1]$不能被集合整除的数的数量

#include<bits/stdc++.h>
using namespace std;
using PII=std::pair<int,int>;
using i64=long long;
void solve(){
	i64 l,r,k;std::cin>>l>>r>>k;
	std::vector<i64> a(k);
	for(auto &x:a)std::cin>>x;
	auto cal=[&](i64 n){
		if(n==0||n==1)return n;
		i64 ans=n;
		for(int i=1;i<1ll<<k;i++){
			i64 cnt=0;__int128 res=1;
			for(int j=0;j<k;j++){
				if(i>>j&1){
					res*=a[j];
					cnt++;
				}
			}
			if(cnt&1){
				ans-=n/res;
			}else{
				ans+=n/res;
			}
		}
		return ans;
	};
	i64 ans=cal(r)-cal(l-1);
	std::cout<<ans<<'\n';
}

signed main(){
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	std::cout<<std::fixed<<std::setprecision(10);
	solve();
	return 0;
}