World Final Training 5——2011-2012 Petrozavodsk Summer Training Camp, Kyiv + Kharkov NU Contest

发布者：edward_mj 于World Final Training 5——2011-2012 Petrozavodsk Summer Training Camp, Kyiv + Kharkov NU Contest留下评论

传送门
Board

然后这是我们

A题TLE到死，然后发现status里面有好多人都是2秒多3秒过的……我们1秒就T了，于是问了一下KADR，得到的回答是：

Hi,Thanks for pointing out this problem! I’ve asked MikeMirzayanov about it and he said there was a bug in the system which was fixed about a month ago. Apparently time limit has been set to 5 seconds for a few months and some people got AC with nonoptimal solutions. I think it is not fair to rejudge their solutions now, but taking into account the fact that this is only a training in the gym, from now on the time limit will be set to 1 second.Problem statement says that the time limit is 2 sec for this problem. However, Codeforces judging servers are faster than servers used on the original contest in Petrozavodsk training camp. That’s why some time limits on Codeforces differ from the ones in statement. You can find the correct time limits in “Problems” tab on the contest page. Sorry for inconvenience.

-.-反正是练习嘛，就这样吧。
记一下A题

先给定一个素数P(P<=10^8)，再给定Q(Q<=10^4)个询问，每个询问给定$$a_i, b_i$$，问$$a_i^x = b_i (mod P)$$的最小解x是多少。

如果啥都不看显然是经典的离散对数问题。
Baby-step Giant-step是其中一个经典解法，但是这个复杂度是$$O(\sqrt{P})$$的。乘起来到10^8还是会T。
用原根$$g^s, g^t$$去分别替掉a和b的话，就变成了$$(g^s)^x = g^t (mod P)$$，也就变成解这个同余方程$$s*x = t (mod (P – 1))$$，这个可以扩展gcd然后算，就不说了。
然后变成怎么求a, b对原根g的指标(也就是求s和t)。这就又回到了离散对数问题，虽然想呵呵，但是仔细想想还是有点不一样的。那就是变成了询问2Q次$$g^x = a (mod P)$$的解，这个底数被固定了。
最开始我们是想打张指标表，但是单纯的O(P)还是会T。
如果TL是5s的话，这里已经足够通过了。
于是我们还是得用Baby-step Giant-step，但是得注意到这个分块的精髓在于让两边的计算量接近。
那么假设我们每个块是S这么大，BSGS的时候就要先打一张S这么大的表，都塞进hash table里面。
然后对于每一个求指标的询问，我们需要扫P/S次，每次都要到hash table里面找一找。
于是打表的复杂度是S，处理询问的复杂度是Q*P/S，为了使总复杂度最小，两边取等号，S = Q*P/S，于是$$S=\sqrt{Q*P}$$，算起来就是S=10^6。
总计算量就是10^6级别了。
于是速度刷到了第一……

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
const int N = 100005;
const int block_size = 800000;
int P, Q, ori;
int a[N], b[N];
map  ind;
lld inv;

namespace HashTable {
	const int HashMod = 10000007;
	int pt;
	struct edge {
		int x, y;
		edge *next;
	}pool[block_size + 5], *ls[HashMod];

	void add(int x, int y) {
		int i = x % HashMod;
		edge *t = &pool[pt++];
		t->x = x;
		t->y = y;
		t->next = ls[i];
		ls[i] = t;
	}

	int in(int x) {
		for (edge *t = ls[x % HashMod]; t; t = t->next)
			if (t->x == x) return t->y;
		return -1;
	}
}

void gao1() {
    for (int i = 0; i < Q; i++) {
        lld t = 1, ret = -1;
        for (int j = 0; j < P; j++) {
            if (t == b[i]) {
                ret = j;
                break;
            } else {
                t = t * a[i] % P;
            }
        }
        cout << ret << endl;
    }
}

int pow_mod(lld a, int b) {
    lld ret = 1;
    for ( ;b; b >>= 1) {
        if (b & 1) ret = ret * a % P;
        a = a * a % P;
    }
    return ret;
}

lld extgcd(lld a, lld b, lld &x, lld &y) {
    lld t, ret;
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    ret = extgcd(b, a % b, x, y);
    t = x;
    x = y;
    y = t - a / b * y;
    return ret;
}

int getind(int x) {
	if (ind.count(x)) return ind[x];
	int t = x;
	for (int i = 0; i < P; i += block_size) {
		int ret = HashTable::in(x);
		if (ret != -1) {
			ind[t] = i + ret;
			return i + ret;
		}
		x = x * inv % P;
	}
	return -1;
}

void init() {
	lld t = 1;
	for (int i = 0; i < block_size && i < P; i++) {
		if (HashTable::in(t) == -1) {
			HashTable::add(t, i);
		}
		t = t * ori % P;
	}
	inv = pow_mod(t, P - 2);
}


int gao2() {
	vector  vec;
    int phi = P - 1;
    for (int i = 2; i * i <= phi; i++) {
        if (phi % i == 0) {
            vec.push_back(i);
            vec.push_back(phi / i);
        }
    }
    for (int i = 2; ; i++) {
        bool flag = 1;
        foreach (it, vec) {
            if (pow_mod(i, *it) == 1) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            ori = i;
            break;
        }
    }
	init();
    for (int i = 0; i < Q; i++) {
        if (a[i] == 0) {
            int ret = -1;
            if (b[i] == 0) ret = 1;
            if (b[i] == 1) ret = 0;
            printf("%d\n", ret);
            continue;
        }
        if (b[i] == 0) {
            printf("-1\n");
            continue;
        }
        if (a[i] == 1) {
            printf("%d\n", b[i] == 1 ? 0 : -1);
        } else if (b[i] == 1) {
            printf("0\n");
        } else {
            lld s = getind(a[i]), t = getind(b[i]), x, y;
            lld g = extgcd(s, phi, x, y);
            if (t % g != 0) {
                printf("-1\n");
            } else {
                lld s=phi/g,ans;
                t/=g;
                x = (x % s+s) %s;
                x=x*t%phi;
                ans=x;
                x = (phi - x) / s * s + x;
                for (int i = 0; i < 5; i++) {
                    x += s;
                    x %= phi;
                    if (x < ans) ans = x;
                }
                cout << ans << endl;
            }
        }
    }
}


int main(){
    freopen("alot.in", "r", stdin);
    freopen("alot.out", "w", stdout);
	scanf("%d%d", &P, &Q);
	for (int i = 0; i < Q; i++) {
		scanf("%d%d", &a[i], &b[i]);
	}
	if (P <= 2) {
		gao1();
	} else {
		gao2();
	}
}

留下评论

您的邮箱地址不会被公开。 必填项已用 * 标注