10 months ago

suryansh jaiswal • 370

Lucknow

Question 1 Solution

#define MAXN 1000001
 
// stores smallest prime factor for every number
int spf[MAXN];
 
// Calculating SPF (Smallest Prime Factor) for every
// number till MAXN.
// Time Complexity : O(nloglogn)
void sieve()
{
    spf[1] = 1;
    for (int i = 2; i < MAXN; i++)
 
        // marking smallest prime factor for every
        // number to be itself.
        spf[i] = i;
 
    // separately marking spf for every even
    // number as 2
    for (int i = 4; i < MAXN; i += 2)
        spf[i] = 2;
 
    for (int i = 3; i * i < MAXN; i++) {
        // checking if i is prime
        if (spf[i] == i) {
            // marking SPF for all numbers divisible by i
            for (int j = i * i; j < MAXN; j += i)
 
                // marking spf[j] if it is not
                // previously marked
                if (spf[j] == j)
                    spf[j] = i;
        }
    }
}
 
// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
vector<ll> getFactorization(ll x)
{
    vector<ll> ret;
    while (x != 1) {
        ret.push_back(spf[x]);
        x = x / spf[x];
    }
    return ret;
}


vector<ll>  primeFactors(ll x)
{
vector<ll> v;
        for(ll i = 2;i*i<=x;i++)
        {
            if(x%i == 0)
            {
                v.pb(i);
                while(x%i == 0)
                {
                    x/=i;
                }
            }
        }
        if(x > 1)v.pb(x);
        return v;
}
bool compare(pair<int,int> a,pair<int,int> b)
{
  
        if(a.first==b.first)
            return a.second<b.second;
        else
            return a.first>b.first;
}

void solve()
{
  int n;
  cin>>n;
  vector<int> v(n);
  f(i,n)
  cin>>v[i];
  int sz=1e6+1;
  vector<int> temp(sz,0);
  for(int i=0;i<n;i++)
  {
    vector<ll> t=getFactorization(v[i]);
    for(auto j:t)
        temp[j]++;
  }
  vector<int> pref(sz,0);
  for(int i=1;i<sz;i++)
  {
    pref[i]=pref[i-1]+temp[i]*temp[i];
  }
  int q;
  cin>>q;
  f(i,q)
  {
    int x,y;
    cin>>x>>y;
    cout<<pref[y]-pref[x-1]<<endl;
  }

  


}
int32_t main()
{
 sieve();   
 solve();        
}

10 months ago

suryansh jaiswal • 370

Lucknow

Question 2 Solution

int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty()) {
            return 0;
        }
        int m = matrix.size(), n = matrix[0].size(), sz = 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!i || !j || matrix[i][j] == '0') {
                    dp[i][j] = matrix[i][j] - '0';
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
                sz = max(dp[i][j], sz);
            }
        }
        return sz * sz;
    }
};

13 months ago

vamshi • 10

Mumbai

 int maxSquare(int n, vector<vector<int>> mat){

       int m=n;
        int ans = *max_element(mat[n-1].begin(), mat[n-1].end());
        for(int i=n-2; i>=0; i--)
            for(int j=m-2; j>=0; j--){
                if(mat[i][j]==1){
                    mat[i][j] = 1 + min(mat[i][j+1], min(mat[i+1][j], mat[i+1][j+1]));
                    ans = max(ans, mat[i][j]);
                }
            }
        return ans;
    }

14 months ago

Manas Bhargava • 0

Mumbai

Were oops and os questions asked?