Gcd of Subarrays codechef solution in c++ || December Long 2022 (Rated for Div 3 & 4)

 

Problem

You are given positive integers $N$ and $K$.

You have to construct an array $A$ of length $N$ such that :

• $1 \leq A_i \leq 10^{18}$
• $\sum_{i=1}^{N} \sum_{j=i}^{N} F(i,j) = K$, where $F(i,j)$ denotes the gcd of all elements of the subarray $A[i, j]$.

If multiple such arrays exist, print any.
Report $-1$ if no such array exists.

Note that $A[l, r]$ denotes the subarray $[A_l ,A_{l+1}, \ldots, A_{r-1}, A_r]$.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of single line of input.
  • The only line of each test case contains two space-separated integers $N$ and $K$ — the number of elements and required sum.

Output Format

For each test case, output on a new line $N$ space-separated integers, denoting array $A$.
Report $-1$ if no such array exists.

code of this question ----- take it as only reference

#include<bits/stdc++.h>

using namespace std;

void solve(){

    long long j,k;

    cin>>j>>k;

    long long min_sum_gcd = j*(j+1);

    min_sum_gcd/=2;

    min_sum_gcd-=1;

    if(k<min_sum_gcd)

    {

        cout<<"-1"<<endl;

        return;

    }

    for(int i=1; i<j; ++i)

    cout<<"1"<<" ";

    

    cout<<k-min_sum_gcd<<endl;

    

  

}

int main()

{

  long long t;

  cin >>t;

  while(t--)

  {

    solve();

  }

  return 0;

   

}