比较赤裸的模线性方程组模型了，给定的模都是两两互素的，可以用扩展欧几里德和孙子定理来解。第一次写这个，不知道健壮性如何，这个题目数据貌似很弱。。
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 @
2009-03-22 09:51 sdfond 阅读(234) |
评论 (0) |
编辑 收藏
基本的判素都比较慢，对于这个题目的BT数据量(2 ^ 31)，也只能用概率判素模型了。
Miller-Rabin基于费马小定理：如果(a, p) = 1，那么a ^ (p - 1) = 1 mod p。满足这个性质的p叫伪素数，如果一个数是伪素数，那么它有很大可能是素数。通过多次的枚举a，利用快速幂取模判断，就可以知道p是不是素数，Miller-Rabin测试的成功率在3/4。
费马小定理是该定理的特殊形式：如果p是素数，那么对于任意整数a：a ^ p = a mod p。这个定理可以用归纳法证明，证明依据这样一个事实：组合数C(n, k)是一个整数，如果n是素数，那么n和k!、(n - k)!的每一项都互素，可以提出n，也就是C(n, k) / n也是整数，所以n | C(n, k)。
这个题目的代码如下：
#include <cstdio>
#include <stdlib.h>
const int MAX = 4, N = 1000000;
long long PowerMod(long long a, long long b, long long k)
{
long long ret = 1, f = a;
while (b)
{
if (b & 1)
ret = ret * f % k;
f = f * f % k;
b >>= 1;
}
return ret;
}
bool MillerRabin(long long n)
{
int i;
long long tmp;
srand(100);
for (i = 0; i < MAX; i++)
{
tmp = rand() % (n - 1) + 1;
if (PowerMod(tmp, n - 1, n) != 1)
break;
}
return (i == MAX);
}
int main()
{
long long n, i, j;
bool tag[N] = {1, 1, 0};
for (i = 2; i * i < N; i++)
{
if (tag[i]) continue;
for (j = i; j * i < N; j++)
tag[j*i] = 1;
}
while (scanf("%lld", &n) == 1)
{
if (n < N)
printf("%s\n", tag[n] ? "NO" : "YES");
else
printf("%s\n", ((n & 1) == 0) || !MillerRabin(n) ? "NO" : "YES");
}
return 0;
}
posted @
2009-03-18 21:15 sdfond 阅读(600) |
评论 (0) |
编辑 收藏也是很赤裸裸的模型，这里求的是绝对值最小解，还有就是用到高精。我用java不会写传引用，因此只好开了全局变量。
import java.math.*;
import java.util.*;
public class Main
{
static public BigInteger x = null, y = null;
static BigInteger extended_gcd(BigInteger a, BigInteger b)
{
BigInteger zero = new BigInteger(new String("0"));
BigInteger ret, tmp;
if (b.compareTo(zero) == 0)
{
x = new BigInteger(new String("1"));
y = zero;
return a;
}
ret = extended_gcd(b, a.mod(b));
tmp = x;
x = y;
y = tmp.subtract(a.divide(b).multiply(y));
return ret;
}
static BigInteger modular_linear_equation(BigInteger a, BigInteger b, BigInteger n)
{
BigInteger e, e2;
BigInteger d = extended_gcd(a, n);
e = b.divide(d).multiply(x).mod(n.divide(d));
e2 = e.subtract(n.divide(d)).abs();
if (e.compareTo(e2) < 0) return e;
return e2;
}
public static void main(String[] args)
{
BigInteger a, b, c;
Scanner in = new Scanner(System.in);
while (in.hasNext())
{
a = in.nextBigInteger();
b = in.nextBigInteger();
c = in.nextBigInteger();
c = c.multiply(new BigInteger(new String("-1")));
System.out.println(modular_linear_equation(a, c, b));
}
}
}
posted @
2009-03-17 20:16 sdfond 阅读(150) |
评论 (0) |
编辑 收藏
最后化成c * x = b - a mod (2 ^ k)，解这个模线性方程，输出最小正解即可。
写程序的时候有了一个误区，以为如果b - a是负的，把它化成正的话那么输出的时候就可以直接模2 ^ k，不用再考虑是负的情况了。但是忽略了x可能为负的情况，所以WA了很多次。其实根本不需考虑b - a的正负性，最后输出的时候加2 ^ k再模2 ^ k就行了。
还有一个是输出最小解，因为最后的所有解模n / d同余，因此直接模n / d即可。
#include <cstdio>
//ax + by = gcd(a, b)
long long extended_gcd(long long a, long long b, long long &x, long long &y)
{
long long ret, tmp;
if (!b)
{
x = 1, y = 0;
return a;
}
ret = extended_gcd(b, a % b, x, y);
tmp = x;
x = y;
y = tmp - a / b * y;
return ret;
}
//ax = b mod n
long long modular_linear_equation(long long a, long long b, long long n)
{
long long x, y, e;
long long d = extended_gcd(a, n, x, y);
if (b % d) return -1;
e = b / d * x % n + n;
return e % (n / d);
}
int main()
{
long long a, b, c, ans;
int k;
while (scanf("%lld %lld %lld %d", &a, &b, &c, &k) == 4)
{
if (a == 0 && b == 0 && c == 0 && k == 0)
break;
ans = modular_linear_equation(c, b - a, 1LL << k);
if (ans == -1)
puts("FOREVER");
else
printf("%lld\n", ans);
}
return 0;
}
posted @
2009-03-17 18:53 sdfond 阅读(1491) |
评论 (2) |
编辑 收藏
这个是经典的Eraosthenes筛法：
for (int i = 2; i * i < N; i++)
{
if (tag[i]) continue;
for (int j = i; i * j < N; j++)
tag[i*j] = 1;
}
for (int i = 2; i < N; i++)
if (!tag[i])
prime[tol++] = i;
但是Eraosthenes筛法的速度并不快，原因在于对于一个合数，这种方法会重复的标记。一种线性筛素数的方法有效的解决了这一点，代码如下：
void get_prime()
{
int cnt = 0;
for (int i = 2; i < N; i++)
{
if (!tag[i]) p[cnt++] = i;
for (int j = 0; j < cnt && p[j] * i < N; j++)
{
tag[i*p[j]] = 1;
if (i % p[j] == 0)
break;
}
}
}
可以用均摊分析的方法来分析这个算法的复杂度：由于每个合数都唯一的被它的最小素因子筛一次，而每个合数的最小素因子都是唯一的，因此总复杂度是O(n)。
这种筛法的思想很强悍，有很多利用价值，可以根据这种方法做到线性筛欧拉函数等等，继续研究中。。
posted @
2009-03-16 21:29 sdfond 阅读(4590) |
评论 (5) |
编辑 收藏