1 条题解

  • 0

    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <deque>
    #include <set>
    #include <limits>
    #include <string>
    #include <sstream>
    #include <thread>
    using namespace std;

    const int oo_min=0xc0c0c0c0,oo_max=0x3f3f3f3f;

    namespace dts
    {
    typedef long long ll;

    ll n,a,b;
    ll rec[15+1];

    ll calc(ll a,ll b,ll key)
    {
    ll l,r;
    if (a%key!=0)
    l=((a/key)+1)*key;
    else
    l=a;
    if (b%key!=0)
    r=(b/key)*key;
    else
    r=b;
    if (l<=r)
    return (r-l)/key+1;
    else
    return 0;
    }

    ll gcd(ll a,ll b)
    {
    if (b==0)
    return a;
    else
    return gcd(b,a%b);
    }

    ll lcm(ll a,ll b)
    {
    return a*b/gcd(a,b);
    }

    void dfs(ll pos,ll num,ll sig,ll *ans)
    {
    *ans+=sig*calc(a,b,num);
    for (ll i=pos+1;i<=n;i++)
    dfs(i,lcm(num,rec[i]),-sig,ans);
    }

    ll work()
    {
    ll temp=8,ans=0;
    dfs(0,temp,1,&ans);
    return ans;
    }

    void main()
    {
    while (~scanf("%lld",&n))
    {
    for (ll i=1;i<=n;i++)
    scanf("%lld",&rec[i]);
    scanf("%lld%lld",&a,&b);
    printf("%lld\n",work());
    }
    }
    };

    int main()
    {
    dts::main();
    }

  • 1

信息

ID
1142
难度
7
分类
组合数学 | 容斥原理数论 点击显示
标签
(无)
递交数
157
已通过
25
通过率
16%
上传者