KLU 24

LINK:   https://www.hackerrank.com/skdece38


1]

IN C

Hyperrectangle GCD

#include <stdio.h>

#define P 1000000007LL

long long I,g,b[1000], r,h,a[2000000],i,j,k,l,m,n, s[2000000],t,min, v[200000];

long long obsah(long long nn)
{
long long vv=1, ii;

for(ii=0;ii<k;ii++) vv = (vv*(b[ii]/nn))%P;

return vv;
}

long long next(long long jj)
{
long long kk,ii, ne;

kk = b[0]/jj;

ne = b[0]/kk + 1;

for(ii=1;ii<k;ii++)
 {
  kk = b[ii]/jj;

   if(ne > b[ii]/kk +1) ne = b[ii]/kk + 1;
 }


return ne;
}


int main()
{

scanf("%lld",&t);

while(t)
{
t--;

scanf("%lld",&k);
for(i=0;i<k;i++) scanf("%lld",b+i);

min = b[0];
for(i=0;i<k;i++) if(min>b[i]) min = b[i];


//printf("zac\n");

//a[0] = 1;
//s[0] = obsah[1];
j = 1;
l = 0;

while(1)
{
//printf("%lld =j\n",j);
a[l] = j;
s[l] = obsah(j);
l++;

if(j>min) break;

j = next(j);
}


for(m=l-1;m>=0;m--)
  {
  v[m] = s[m];

  i = 2;
  h = 1;

  while(i*a[m] <= min)
   {

   while(a[m]*i >= a[h+1]) h++;

//  printf("%lld=m %lld=i %lld=h\n",m,i,h);

   I = (a[h+1]-1)/a[m];

   g = (I-i+1);

//  printf("%lld=m %lld=i %lld=h %lld=I %lld=g\n",m,i,h,I,g);

// return 0;

   v[m] = (v[m] - v[h]*g)%P;

   i=I+1;
   }

   v[m] = (v[m]+P)%P;
  }


//for(i=0;i<l;i++) printf("%lld: %lld %lld -> %lld\n", i, a[i], s[i], v[i]);

  r = 0;
  i = 1;
  h = 0;

  while(i <= min)
   {
//   printf("...%lld=i %lld=h\n",i,h);

   while(i >= a[h+1])
     {
      h++;
//      printf("kkk\n");
     }

   I = a[h+1]-1;

   g = (I-i+1)*(I+i)/2;

//  printf("....%lld=m %lld=i %lld=h %lld=I %lld=g\n",m,i,h,I,g);

// return 0;

   r = (r + v[h]*g)%P;

   i=I+1;
   }

   printf("%lld\n",r);




}



return 0;
}





2]

IN C

Lego Blocks

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define MOD 1000000007
#define MAX 1001

 int N, M,i,j,nPieces = 4;
int pieces[] = {1, 2, 3, 4};
long long RowComb[MAX],ColumnComb[MAX],ColumnCombWithNoHoles[MAX];

void logic()
{
    scanf("%d %d",&N,&M);
 
    memset(RowComb, 0, sizeof(RowComb));
    RowComb[0] = 1;
    for (i = 1; i <= M; i++) {
        for (j = 0; j < nPieces; j++) {
            if (i - pieces[j] >= 0)
                RowComb[i] = (RowComb[i]+RowComb[i - pieces[j]]) % MOD;
        }
    }

    for (i = 1; i <= M; i++) {
        long long res = 1;
        for (j = 1; j <= N; j++) {
            res = (res *RowComb[i]) % MOD;
        }
        ColumnComb[i] = res;
    }
    ColumnCombWithNoHoles[1] = ColumnComb[1];
    for (i = 2; i <= M; i++) {
        ColumnCombWithNoHoles[i] = ColumnComb[i];
        for (j = 1; j < i; j++) {
            ColumnCombWithNoHoles[i] = (MOD + ColumnCombWithNoHoles[i]-(ColumnCombWithNoHoles[j] * ColumnComb[i - j]) % MOD) % MOD;
        }
    }

    printf("%lld\n",ColumnCombWithNoHoles[M]);
    
}

int main() {
    int T;
scanf("%d",&T);
while(T--) logic();
    return 0;
}


3]

IN C

Largest Non-Coprime Submatrix