比較赤裸的模線性方程組模型了，給定的模都是兩兩互素的，可以用擴展歐幾里德和孫子定理來解。第一次寫這個，不知道健壯性如何，這個題目數據貌似很弱。。
TJU 3027
#include <cstdio>
const int N = 8;
void extended_gcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1;
y = 0;
return;
}
extended_gcd(b, a % b, x, y);
int tmp = x;
x = y;
y = tmp - a / b * y;
}
int modular_linear_equation_system(int b[N], int m[N], int n)
{
int M = 1, x, y, ret = 0;
for (int i = 0; i < n; i++)
M *= m[i];
for (int i = 0; i < n; i++)
{
extended_gcd(M / m[i], m[i], x, y);
ret += M / m[i] * x * b[i];
}
while (ret <= 0) ret += M;
while (ret > M) ret -= M;
return ret;
}
int main()
{
int m[N], b[N], T, n, tmp, ans;
const int num = 4, numc = 3;
char str[N], hash[30] = " ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = 0; i < num; i++)
scanf("%d", &m[i]);
for (int j = 0; j < n; j++)
{
scanf("%d", &tmp);
for (int i = 1; i <= num; i++)
{
b[num-i] = tmp % 100;
tmp /= 100;
}
ans = modular_linear_equation_system(b, m, num);
for (int i = 1; i <= numc; i++)
{
str[numc-i] = hash[ans%100];
ans /= 100;
}
str[numc] = '\0';
if (j == n - 1)
{
int k = numc - 1;
for (; k >= 0; k--)
if (str[k] != ' ')
break;
str[k+1] = '\0';
}
printf("%s", str);
}
putchar('\n');
}
return 0;
}
posted on 2009-03-22 09:51
sdfond 閱讀(280)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm - Number Theory