Untitled
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