Skip to content

Instantly share code, notes, and snippets.

@rodrigoalvesvieira
Created March 20, 2014 14:52
Show Gist options
  • Save rodrigoalvesvieira/9665568 to your computer and use it in GitHub Desktop.
Save rodrigoalvesvieira/9665568 to your computer and use it in GitHub Desktop.
#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;
}
/*
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment