自选题解题解

1、er Modulo Inverted解题江苏省常州高级中学February 25, 201111题目大意给出 a b 和 p， ax b (mod p)，求最小的 x。这其实是一个很 的模型，离散对数。2当 p 是质数的情况先看一个特殊的情况，当 p 为质数。一个直观的想法是枚举 x，然后计算 ax mod p。但是当 p 十分大的时候，这个算法可能达到O(P ) 的复杂度，不是很理想。解决这个问题的关键是预处理部分 at，然后枚举 + 查表。令 m = p，那么 x 一定可以表示成 im + j ，其中 0 i, j m发现 i 和 j 都是不超过 m 的自然数，于是只要预处理 aj, j

2、m，然后枚举一个 i，可以很快计算出 aim，不妨令其为 A，问题转化为求出是否有一个 j 满足 A aj b mod p。由于 p 是质数，只要求出 A1 mod p，就可以在 O(1) 的时间内查找 hash 表解决。预处理的复杂度是 O(p)，枚举同样也是 O(p)。这是一个高效的算法。3当 p 不是质数的情况当 p 不是质数呢？这个算法是不适合的，为什么？回想刚才算法的本质，就是要求 A1 mod p。在 p 是质数的情况下 A1 是唯一的，但是当 p 不是质数的时候就不同了。那可以枚举这个 A1 吗？是否定的，因为 A1 可能很多，数量是 O(A, p) 的。须减少 A1 的数量。令

3、 d =(a, p)，来看 ax b mod p。如果 b mod d = 0 显然无解。那么 a = ad, p = pd, b = bd，等式变为adx = bd mod pd显然他等价于ax = b mod p(1)(2)也就是 aax = b mod p 且(a, p) = 1这样又回到了刚才 ax = b mod p 的形式。于是不断消去因子 d，直到 d=1，也就是原来的A1 只有一个解为止。2但是这样做对于 x log P 可能有 bug，这显而易见，于是只要先上面的消法求解就 OK 了。枚举到 a50，然后再用这个解法和问题一其实是同一的，因为问题一的做。(a, p) = 1，

4、等于一次也没有消除就直接4代码#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include#includeusing namespatd;#define #define #define #define #define #defin #define #define #

5、define #define #define #define #define #defineME(s) memset(s),0, sizeof(s)MM(s,a) memset(s),(a),sizeof(s)MCP(s,a) memcpy(s), (a), sizeof(s) LL long longLD long doubleI pairPDD pair mkp(a,b) make_pair(a),(b) yx secondsqr(a) (a)*(a)lowbit(x) (x)&(-(x) two(x) (1=1;return ret;LLextend_(LL a,LL b,LL &x,L

6、L &y)if(b=0)x=1;y=0;return a;LL _y,_x;LL g=extend_ x=_x;y=_y-a/b*_x; return g;(b,a%b,_y,_x);LLinv(LL a,LL n) LL x=0,y=0;/(a,n)=1LL g=extend_(a,n,x,y);return (x%n+n)%n;run() a%=p; b%=p;t=1%p;for(i=0;i1)if(b%d!=0)return fpr b/=d;p/=d; D=D*(LL)(a/d)%p; cnt+;f(fout,No Solutionn);m=(map M;for(i=0;im;i+)if(M.find(t)=M.end()Mt=i;t=t*(LL)a%p;K= t=D;for(_mod();i=0;im;i+) tr=inv(LL)t,p);w=b*(LL)tr%p; if(M.find(w)!=M.end()return fprf(fout,%dn,Mw+i* t=K*(