C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2020-07-02 22:05:20

#include<cstdio>
 
typedef long long ll;
ll n,a,b,ans,s[20];
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
 
void dfs(ll x,ll p,ll t){
  if(t>b)return;
  if(x%2==0)ans+=b/t-a/t;
  else ans-=b/t-a/t;
  for(int i=p+1;i<=n;i++)
    dfs(x+1,i,lcm(t,s[i]));
  return;
}
 
int main(){
  scanf("%lld",&n);
  for(int i=1;i<=n;i++)scanf("%lld",&s[i]);
  scanf("%lld%lld",&a,&b);
  a--;
  dfs(0,0,8);
  printf("%lld\n",ans);
  return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 484K, 提交时间: 2020-06-29 20:40:17

#include<bits/stdc++.h>
using namespace std;
#define ll long long
 
const int MAXN = 20;
ll N,a,b,ans;
ll num[MAXN];
ll lcm(ll a,ll b){return a*b/__gcd(a,b);}
 
void dfs(ll x,ll p,ll t)
{
    if(t>b) return;
    if(x%2==0) ans+=b/t-a/t;
    else ans-=b/t-a/t;
    for(int i=p+1;i<=N;i++)
        dfs(x+1,i,lcm(t,num[i]));
}
 
int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
        scanf("%lld",num+i);
    cin>>a>>b;
    a--;
    dfs(0,0,8);
    cout<<ans;
}