Untitled

 avatar
unknown
c_cpp
2 months ago
2.9 kB
6
Indexable
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
typedef long long int ll;
typedef long double ld;
 
#define fast ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define pb push_back
#define mp(x,y) make_pair(x,y)
#define pi  3.141592653589793238462643383279502884L
#define size(x) x.size()
#define endl "\n"
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define f first
#define s second
const ll N=1e6+5;
const ll INF=1e18;
const ll MIN=-1e18;
const ll MOD=998244353;
const ll MAX=1000001;
const ll P=9973;
const ll P1=998244353;
ll lcm(ll a, ll b) {return (a * b)/__gcd(a , b);}
ll inv(ll N) {if(N==1) return 1; return (MOD-((MOD / N)*inv(MOD % N))% MOD)%MOD;}
#define ordered_set tree<pair<ll,ll>,null_type,less<pair<ll,ll>>,rb_tree_tag,tree_order_statistics_node_update>
 
ll lp[N];
 
ll get(ll n, vector<ll> pr){
    if(n <= 1)return 0;
    ll res = 0;
    for(ll i=1; i<(1<<size(pr)); i++){
        ll prod = 1;
        for(ll j=0; j<size(pr); j++)
            if(i&(1ll<<j))prod *= pr[j];
        if(__builtin_popcount(i)%2)res += (n/prod);
        else res -= (n/prod);
    }
    return res;
}
vector<ll> getprimes(ll x){
    set<ll> primes1;
    while(x > 1){
        primes1.insert(lp[x]);
        ll t = lp[x];
        while(x%t == 0)x/=t;
    }
    vector<ll> pr;
    for(auto e:primes1) pr.pb(e);
    return pr;
}
 
vector<ll> LCM(ll x, ll y){
    vector<ll> X = getprimes(x), Y = getprimes(y), res;
    set<ll> st;
    for(auto e: X) st.insert(e);
    for(auto e: Y) st.insert(e);
    for(auto e: st){
        res.pb(e);
    }
    return res;
}
vector<ll> LCM(ll x, ll y, ll z){
    vector<ll> X = LCM(x,y), Y = getprimes(z), res;
    set<ll> st;
    for(auto e: X) st.insert(e);
    for(auto e: Y) st.insert(e);
    for(auto e: st){
        res.pb(e);
    }
    return res;
}
 
void solve(){
    ll x,y,z,l,r; 
    cin>>x>>y>>z>>l>>r;
    ll resx =(r - l + 1)-(get(r, getprimes(x))-get(l - 1, getprimes(x)));
    ll resy =(r - l + 1)-(get(r, getprimes(y))-get(l - 1, getprimes(y)));
    ll resz =(r - l + 1)-(get(r, getprimes(z))-get(l - 1, getprimes(z)));
    ll resxy =(r - l + 1)-(get(r, LCM(x, y))-get(l - 1, LCM(x, y)));
    ll resxz =(r - l + 1)-(get(r, LCM(x, z))-get(l - 1, LCM(x, z)));
    ll resyz =(r - l + 1)-(get(r, LCM(y, z))-get(l - 1, LCM(y, z)));
    ll resxyz =(r - l + 1)-(get(r, LCM(x, y, z))-get(l - 1, LCM(x, y, z)));
    ll ans =resx + resy + resz - resxy - resxz - resyz + resxyz;
	cout<<ans<<endl;
 
}
 
 
int main(){
    fast;
    int t=1;
    for(int i=2; i<N; i++){
    	if(lp[i])continue;
    	for(int j=i; j<N; j+=i)
    		lp[j] = i;
    }
    //cin>>t;
    while(t--){
        solve();
    }
}
Editor is loading...
Leave a Comment