Question

write a Chinese remainder program in c and java with an output

by using these instructions

Answer 1

In c language:-

#include<stdio.h>

#include<stdlib.h>

long long int MultiplicativeInverse(long long int e,long long int mod)

{

    long long int i;

    for(i=1;i<mod;i++)

        if((e*i)%mod==1)

            return i;

}

int main()

{

    long long int i,n,*a,*b,*m,M,*Marray,answer;

    printf("Enter the number of Equations : \n");

    scanf("%lld",&n);

    a=(long long int*)malloc(sizeof(long long int)*n);

    m=(long long int*)malloc(sizeof(long long int)*n);

    Marray=(long long int*)malloc(sizeof(long long int)*n);

    printf("Enter the array a :\n");

    for(i=0;i<n;i++)

        scanf("%lld",&a[i]);

    printf("Enter the array m (all the elements of m should be pairwise co-prime) :\n");

    for(i=0;i<n;i++)

        scanf("%lld",&m[i]);

    M=1;

    for(i=0;i<n;i++)

        M*=m[i];

    for(i=0;i<n;i++)

        Marray[i]=M/m[i];

    answer=0;

    for(i=0;i<n;i++)

        answer = (answer + ((a[i] * Marray[i])%M * MultiplicativeInverse(Marray[i],m[i]))%M)%M;

    printf("x = %lld\n",answer);

    return 0;

}

Input:

m[] = { 3, 5, 7 };
 a[] = { 2, 3, 2 };

Output: 23

In java:

import java.io.*;

class GFG {

static int inv(int a, int m)

{

int m0 = m, t, q;

int x0 = 0, x1 = 1;

if (m == 1)

return 0;

while (a > 1)

{

q = a / m;

t = m;

m = a % m;a = t;

t = x0;

x0 = x1 - q * x0;

x1 = t;

}

if (x1 < 0)

x1 += m0;

return x1;

}

static int findMinX(int num[], int rem[], int k)

{

int prod = 1;

for (int i = 0; i < k; i++)

prod *= num[i];

int result = 0;

for (int i = 0; i < k; i++)

{

int pp = prod / num[i];

result += rem[i] * inv(pp, num[i]) * pp;

}

return result % prod;

}

public static void main(String args[])

{

int num[] = {3, 4, 5};

int rem[] = {2, 3, 1};

int k = num.length;

System.out.println("x is " +findMinX(num, rem, k));

}

}

Output: 11