BF21JB - Editorial

PROBLEM LINK:

[Practice ]( Crossbow | CodeChef)

Setter: Aritra Banerjee
Tester: Rounak Das
Editorialist: CodeChef CIEM Chapter

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Ad-hoc

PROBLEM:

You are given an integer D. Find an integer sequence A1​,A2​,…,AN​ such that the following conditions are satisfied:

  • 1≤N≤10^5
  • 1≤A_i≤10^5 for each valid ii
  • ∑_{i=1}^{N}∑_{j=i}^{N}(min(A_i,A_{i+1},…,A_j)−GCD(A_i,A_{i+1},…,A_j))=D

SOLUTION :

#include <stdio.h>

int main(){
long t,d,q,r,n,a[100000],i;
n=0;
scanf("%ld",&t);
while(t--){
    scanf("%ld",&d);
    q=d/((long)1e5-2);
    r=d%((long)1e5-2);
    //printf("%ld %ld %ld\n",d,r,q);
    for(i=0;i<q;i++){
        a[3*i]=(long)1e5;
        a[3*i+1]=(long)1e5-1;
        a[3*i+2]=1;
        n=3*i+3;
    }
    a[n]=r+2;
    a[n+1]=r+1;
    n+=2;
    printf("%ld\n",n);
    for(i=0;i<n;i++)
        printf("%ld ",a[i]);
    printf("\n");
    n=0;
}
return 0;
}