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;
}