Playing with GCD

problem statement is here

#include<stdio.h>

long long ar[100004];

void etf(){

     long long k,i,z;

     ar[0]=0;

     for(k=1;k<100001;k++){

      long long n=k;

      long long r=n;

        for(i=2;i*i<=n;i++){ 

          if (n%i==0) 

          r-=r/i; 

          while(n%i==0) 

          n/=i; 

       } 

       if (n>1)

        r-=r / n; 

       z=k-r;

       ar[k]=ar[k-1]+z;

   } 

}

int main(){

    long long t,num,c=1;

    etf();

    scanf("%lld",&t);

    while(t--){

        scanf("%lld",&num);

        printf("Case %lld: %lld\n",c,ar[num]);

        c++;

    }

    return 0;

}

Game of chocolate

problem statement is here

#include<stdio.h>

long long gcd(long long a,long long b){

    if(b==0){

        return a;

    }

return gcd(b,a%b);

}

int main(){

long long a,b,c,d,e,f,g,i,j,cc=1,t;

scanf("%lld",&t);

while(t--){

scanf("%lld %lld %lld %lld",&a,&b,&c,&d);

e=a*(c+1)+b*(d+1);

        f=(a+b)*(c+1+d);

        g=gcd(e,f);

        if(g>0){

        e/=g;

        f/=g;

        }

        if(e==0){

        printf("Case %lld: 0\n",cc);

        }else{

        printf("Case %lld: %lld/%lld\n",cc,e,f);

        }

        cc++;

}

return 0;

}

Rivals

problam statement is here

#include<stdio.h>

#define MOD 1000000007

long long ar[2000010];

void fact(){

long long i;

    ar[0]=1;

    ar[1]=1;

    for(i=2;i<=2000000;i++)

        ar[i]=(ar[i-1]*i)%MOD;

}

long long fermet(long long x){

    long long a=1,p=x,n=MOD-2;

    while(n){

        if(n&1)

            a=(a*p)%MOD;

        p=(p*p)%MOD;

        n>>=1;

    }

    return a;

}

int main(){

    int t,a,b;

    long long c,d;

    fact() ;

    scanf("%d",&t);

    while(t--){

        scanf("%d %d",&a,&b);

        c=(fermet(ar[a])*fermet(ar[b]))%MOD;

        d=(ar[a+b]*c)%MOD;

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

    }

    return 0;

}

Balanced base-3

problem statement is here

#include<stdio.h>

int main() {

int t,y,z,n,ar[10000],i;

scanf("%d",&t);

while(t--){

scanf("%d",&n);

z=0;

while(n){

ar[z]=n%3;

z++;

n/=3;

}

ar[z]=0;

for(i=0;i<=z;i++){

if(ar[i]==2){

ar[i]=-1;

ar[i+1]++;

}else if(ar[i]==3){

ar[i]=0;

ar[i+1]++;

}

}

y=0;

for(i=z;i>=0;i--){

if(ar[i]!=0){

y=1;

if(ar[i]==1) 

printf("+");

else if(ar[i]==-1)

printf("-");

}

else if(y==1) 

printf("0");

}

printf("\n");

}

return 0;

}

Tulip And Numbers

problem statement is here

#include<stdio.h>
int main(){
int a,b,c,d,i,j,n,m,t,ar,x=1,br[100005];
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
scanf("%d",&ar);
a=ar;
br[0]=0;
br[1]=1;
for(i=1;i<n;i++){
scanf("%d",&ar);
if(a==ar){
br[i+1]=br[i];
}else{
br[i+1]=br[i]+1;
a=ar;
}
}
printf("Case %d:\n",x);
x++;
for(i=0;i<m;i++){
scanf("%d %d",&a,&b);
if(a==1){
c=br[b];
}else{
if(br[a]==br[a-1]){
c=br[b]-br[a-1]+1;
}else{
c=br[b]-br[a-1];
}
}
printf("%d\n",c);
}

}
return 0;
}