HackerEarth Glowing Bulbs problem solution

In this HackerEarth Glowing Bulbs problem solution, There is an infinite series of bulbs indexed from 1. And there are 40 switches indexed from 1 to 40. Switch with index x is connected to the bulbs with indexes that are multiple of x. i.e switch 2 is connected to bulb 4, 6, 8 ….

You can easily observe that some bulbs are connected to multiple switches and some are not connected to any switch.

Chotu is playing with these switches, he wants to know the Kth glowing bulb from the start if certain switches are in ON state. If any of the switch is ON, connected to any bulb then bulb starts glowing. But chotu has special fond of prime numbers so he only puts prime indexed switches ON.

HackerEarth Glowing Bulbs problem solution.

#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define P(x) printf("%dn",x)

typedef long long int LL;

vector<int > primes;

LL f(LL x) {

    int sz = primes.size();
    LL res = 0;
    rep(i,1,1<<sz) {
        LL p = 1;
        int sign = -1;
        rep(j,0,sz) if((i>>j)&1) {
            p *= primes[j];
            sign *= -1;
        }
        res += sign * (x/p);
    }

    return res;

}

LL solve(LL k) {

    LL ans = 1;
    LL lo = 1;
    LL hi = 1000000000000000000LL;
    while(lo <= hi) {

        LL mi = (lo + hi) >> 1;
        if(f(mi) >= k) {
            ans = mi;
            hi = mi-1;
        } else {
            lo = mi+1;
        }

    }

    return ans;

}

int main() {
    int t;
    S(t);
    while(t--) {
        string s;
        cin >> s;
        LL k;
        cin >> k;
        primes.clear();
        rep(i,0,s.size()) if(s[i] == '1') {
            primes.push_back(i+1);
        }
        cout << solve(k) << endl;
    }

    return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

int n;

inline void fiu(unsigned long long int *a)
{
 register char c=0;
 while (c<33) c=getchar_unlocked();
 *a=0;
 int tmp = 0;
 while (c>33)
 {
     if ( c == 45 ) tmp = 1;
     else *a=*a*10+c-'0';
     c=getchar_unlocked();
 }
 if ( tmp == 1 ) *a = 0-(*a);
}

inline void fi(int *a)
{
 register char c=0;
 while (c<33) c=getchar_unlocked();
 *a=0;
 int tmp = 0;
 while (c>33)
 {
     if ( c == 45 ) tmp = 1;
     else *a=*a*10+c-'0';
     c=getchar_unlocked();
 }
 if ( tmp == 1 ) *a = 0-(*a);
}
long long f(unsigned long long X, vector <unsigned long long> v)
{
    long long ans = 0;
    for ( int i = 1; i < (1<<n); i++ ) {
        long long pro = 1;
        for ( int j = 0; j < n; j++ ) {
            if ( i&(1<<j) ) pro = pro*v[j];
        }
        int parity = __builtin_popcount(i);
        if ( parity&1 ) ans += X/pro;
        else ans -= X/pro;
    }   
    return ans;
}

int main()
{
    int t;
    unsigned long long K,val,L,R,mx,mid;
    fi(&t);
    while ( t-- ) {
        string s;
        vector <unsigned long long> v;
        cin >> s;
        fiu(&K);
        for ( int i = 0; i < 40; i++ ) {
            if ( s[i] == '1' ) v.push_back((long long)(i+1));
        }
        n = (int)v.size();
        L = 1LL;
        R = (long long)(1e19);
        while ( L <= R ) {
            mid = (L+R)/2;
            val = f(mid,v);
            if ( val == K ) {
                 mx = 0;
                 for ( int i = 0; i < n; i++ ) {
                     mx = max(mx, (mid/v[i])*v[i]);
                 }
                 printf("%llun", mx);
                 break;
            }
            else if ( val > K ) R = mid-1;
            else L = mid+1;
        }
    }
    return 0;
}

coding problems