chinese.cpp

#include <stdio.h>

/*
    Rodrigo Alves @ CIn - rav2
    cin.ufpe.br/~rav2

    Assuming you have downloaded both the C++ and the input file,
    to run this software open your computer's console and run:

    g++ -o chinese.out chinese.cpp && ./chinese.out

    Edit the chinese-in.txt file if you want to add new test cases
    Or just comment out the freopen line in the main() method to
    enter data from the console instead of using the input file.
*/

/*
    A = B (mod m) <=> A (mod m) = B (mod m)
    Check if A - B (mod m) == 0
*/
bool congruent(int a, int b, int m)
{
    return ((a - b) % m) == 0;
}

int main()
{
    freopen("chinese-in.txt", "r", stdin);

    int N, X, m;
    int M1, M2, M3;
    int a1, a2, a3;
    int y1, y2, y3;
    int m1, m2, m3;

    scanf("%d", &N);

    while (N--) {
        scanf("%d %d", &a1, &m1);
        scanf("%d %d", &a2, &m2);
        scanf("%d %d", &a3, &m3);

        m = m1 * m2 * m3;

        M1 = m/m1;
        M2 = m/m2;
        M3 = m/m3;

        for (int i = 1; i <= M1; i++) {
            if (congruent(M1, i, m1)) {
                y1 = i;
                break;
            }
        }

        for (int i = 1; i <= M2; i++) {
            if (congruent(M2, i, m2)) {
                y2 = i;
                break;
            }
        }

        for (int i = 1; i <= M3; i++) {
            if (congruent(M3, i, m3)) {
                y3 = i;
                break;
            }
        }

        X = a1 * M1 * y1 + a2 * M2 * y2 + a3 * M3 * y3;
        int answer = 1;

        for (int i = 1; i <= X; i++) {
            if (congruent(X, i, m)) {
                answer = i;
                break;
            }
        }

        // printf("y1 = %d, y2 = %d and y3 = %d\n", y1, y2, y3);
        // printf("M = %d\n", m);
        // printf("X = %d\n", X);
        printf("%s %d\n", "The Answer is", answer);
    }

    return 0;
}

mod.cpp

/*

Theorem: Let a and b be integers, and let m be a positive integer.
Then a = b (mod m) if and only if a (mod m) = b (mod m)

Theorem: Let m be a positive integer. The integers a and b are congruent modulo m if
and only if there is an integer k such that a = b + km

Determine whether 17 is congruent to 5 modulo 6 and whether 24 and 14 are congruent modulo 6
*/

#include <stdio.h>

bool congruent(int a, int b, int m)
{
    return ((a - b) % m) == 0;
}

int main()
{
    freopen("mod-in.txt", "r", stdin);
    int A, B, M;

    while(scanf("%d %d %d", &A, &B, &M) != EOF) {
        printf("%d = %d (mod %d): ", A, B, M);
        congruent(A, B, M) ? printf("%s\n", "yes") : printf("%s\n", "no");
    }

    return 0;
}