lnicola
6/24/2014 - 9:04 AM

## Some Chinese Remainder Theorem code

Some Chinese Remainder Theorem code

``````#include <iostream>
#include <string>
#include <vector>

int gcd(int u, int v) {
int t;
while (v) {
t = u;
u = v;
v = t % v;
}
return u < 0 ? -u : u; /* abs(u) */
}

bool check(int *c, int *values, int length)
{
for (int i = 0; i < length; i++)
if (values[i] <= c[i])
return false;

for (int i = 0; i < length - 1; i++)
for (int j = i + 1; j < length; j++)
{
auto g = gcd(values[i], values[j]);
if (c[i] % g != c[j] % g)
return false;
//if (gcd(values[i], values[j]) != 1)
//	return false;
}
return true;
}

unsigned long long chirem(int *c, int *m, int n) {
int i, j;
unsigned long long x(0);
std::vector<unsigned long long> M(n), b(n);
for (i = 0; i < n; ++i)
if (c[i] < m[i])
c[i] %= m[i];

for (i = 0; i < n; ++i) {	// Gets M's
if (i == 0) {
M[0] = m[1];
//M.push_back(m[1]);
j = 1;
}
else {
M[i] = m[0];
//M.push_back(m[0]);
j = 0;
}
while (++j < n)
if (i != j)
M[i] *= m[j];
}
for (i = 0; i < n; ++i) {	// Gets b's
j = 0;
while ((M[i] * ++j) % m[i] != 1 && j > 0) {}
if (j < 0)
return -1;
else
b[i] = j;
}
for (i = 0; i < n; ++i)
x += c[i] * b[i] * M[i];	// Finds a number that works
return x % (M[0] * m[0]);	// Finds a number less than PI m.
}

unsigned long long get_score(unsigned long long z1, unsigned long long z2, int i, int j, int k)
{
auto s = std::to_string(z1).size() + std::to_string(z2).size();
if (i != 0)
s += std::to_string(i).size() + 1;
if (j != 1)
s += std::to_string(j).size() + 3;
if (k != 0)
s += std::to_string(k).size() + 2;
return s;
}

void foo(int c1[], int c2[])
{
int v[] = { 'M', 'D', 'C', 'L', 'X', 'V', 'I' };
int n = _countof(v);

unsigned long long best_score = ~0LL;
int best_i, best_j, best_k;

for (int i = -1000; i < 1000; i++)
for (int j = 1; j < 2; j++)
for (int k = -1000; k < 1000; k++)
{
int s[_countof(v)];

for (int t = 0; t < n; t++)
{
char ch = v[t];
ch += i;
ch *= j;
ch += k;
s[t] = ch;
}
//s[t] = (v[t] + i) * j + k;

if (check(c1, s, n)/* && check(c2, s, n)*/)
{
auto z1 = chirem(c1, s, n);
auto z2 = chirem(c2, s, n);
auto score = get_score(z1, z2, i, j, k);
if (score < best_score)
{
best_score = score;
best_i = i;
best_j = j;
best_k = k;

std::cout << "yay " << i << ' ' << j << ' ' << k << ' ' << ' ' << z1 << ' ' << z2 << ' ' << score << std::endl;
}
}

}

}

void bar(int c1[])
{
int v[] = { 'M', 'D', 'C', 'L', 'X', 'V', 'I' };
int n = _countof(v);

for (auto k = 1 ; k < 1000000000; k++)
{
auto ok = true;
for (int i = 0; i < n; i++)
if (k % v[i]%7 != c1[i])
{
ok = false;
break;
}
if (ok)
std::cout << k << std::endl;
}
}

int main()
{
for (auto c = "MDCLXVI"; *c; c++)
{
auto v = (*c&15) * 2 +5;
auto e2 = 833109565 % v;
auto d = 19147339 % v;
auto k = 1; for (; d--; k*=5);
std::cout << *c << ' ' << (1 << e2) *k << std::endl;
}

int c1[] = { 3, 6, 2, 5, 1, 4, 0 };
int c2[] = { 0, 0, 0, 0, 0, 0, 0 };
bar(c1);

//for (auto c = "MDCLXVI"; *c; c++)
//{
//	auto v = *c * 2 - 105;
//	auto e2 = 257708304605 % v;
//	auto d = 401329224880 % v;
//	std::cout << *c << ' ' << (1 << e2) - d << std::endl;
//}

//int c1[] = { 24, 12, 28, 14, 6, 3, 0 };
//int c2[] = { 10, 9, 7, 6, 4, 3, 0 };
//foo(c1, c2);
}
``````