比較赤裸的模線性方程組模型了，給定的模都是兩兩互素的，可以用擴展歐幾里德和孫子定理來解。第一次寫這個，不知道健壯性如何，這個題目數據貌似很弱。。
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 閱讀(279) |
評論 (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 閱讀(641) |
評論 (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 閱讀(187) |
評論 (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 閱讀(1543) |
評論 (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 閱讀(4664) |
評論 (5) |
編輯 收藏