ICPC 的压轴格基约化题目，其实只要这样做！

经常打 ICPC 的朋友想必都知道，出题人偶尔会出格基约化的板子，全然不顾这个东西其实主要的应用领域是求解 CTF 的格密码题目（更多细节可以查看我的博客CTF 记录，搜索关键字LLL，好在这样干的出题人并不多），而实际上，当格子大小很小的时候，在部分情况下，并不需要搬运冗长无味的板子，而可以创造性的用类欧几里得算法这一简单的知识快速求解此题。

类欧几里得在这里干什么？

实际上，用最朴素的类欧几里得+二分就可以在 $O(\log^2)$ 的时间求解如下问题：

$\max\limits_{i=0}^n(ai+b)\bmod p$ 和 $\min\limits_{i=0}^n(ai+b)\bmod p$ ，方法是搬运一个求解 $\sum_{i=0}^n\lfloor(ai+b)/c\rfloor$ 的类欧几里得板子：

ll like_gcd(ll a,ll b,ll c,ll n) {
    if(a==0)return b/c*(n+1);
    if(a>=c||b>=c)return n*(n+1)/2*(a/c)+(n+1)*(b/c)+like_gcd(a%c,b%c,c,n);
    ll m=(a*n+b)/c;
    if(m==0)return 0;
    return n*m-like_gcd(c,c-b-1,a,m-1);
}

再通过计算：$$\sum_{i=0}^n\lfloor (ai+b)/p\rfloor-\lfloor (ai+b-k)/p\rfloor$$ 来判断是否有 $(ai+b)\bmod p\le k$，二分即可：

ll l=0,r=p,gi=like_gcd(a,b,p,n);
while(l+1<r)
{
    ll mid=(l+r)/2;
    if(like_gcd(a,b-mid+p,p,n)==gi)r=mid;
    else l=mid;
}

当然，我们也有 $\log$，在我合作改编出的某道不知名集训队胡策题中，我提出了 $O(\log)$ 的解法，作为这题的最后一档部分分：详细见我的博客。

简单来讲，设：

$$f(a,b,c,n)=\min\limits_{i=0}^n\{(ai+b)\bmod c\}$$

$$g(a,b,c,n)=\max\limits_{i=0}^n\{(ai+b)\bmod c\}$$

以下代码可以 $O(\log)$ 求解 $f,g$，后面我也会用这样的办法，但是请记住 $O(\log^2)$ 也可以接受：

ll g(ll,ll,ll,ll);
ll f(ll a,ll b,ll c,ll n)
{
    a%=c,b%=c;
    ll m=(a*n+b)/c;
    return !a||!n||!m?b:min(b,a-1-g(c,c-b-1,a,m-1));
}
ll g(ll a,ll b,ll c,ll n)
{
    a%=c,b%=c;
    ll m=(a*n+b)/c;
    return !a||!n||!m?a*n+b:max((a*n+b)%c,c-1-f(c,c-b-1,a,m-1));
}

talk is cheap, show you the problem!

SQRT Problem

ICPC2023 区域赛的压轴题，毫无意义的套壳，不清楚为什么要这样做。

简单来讲，求解二次剩余 $x^2\equiv a\pmod n$ 的一个解，已知有一个解满足 $x\in[\lceil\sqrt{b^3}\rceil,\lfloor\sqrt{(b+1)^3-1}\rfloor]$，其中 $0\le b\text< n$，且 $1\le x< n$。

$n$ 十进制下是 $100$ 位，常规求解二次剩余的办法肯定行不通（因为要分解 $n$，这个过程会超时），设 $u=\lceil\sqrt{b^3}\rceil$，$y=x-u$，则 $y\in[0,\lfloor\sqrt{(b+1)^3-1}\rfloor-\lceil\sqrt{b^3}\rceil]$，分析知 $y=O( \frac{3b^{2}+3b}{\sqrt{\left(b+1\right)^{3}-1}+\sqrt{b^{3}}})=O(\sqrt b)$，又因为 $\sqrt {b^3}=O(n)$，所以 $y=O(n^{1/3})$。

简单来讲，我们要求解 $y^2+2uy+u^2-a\equiv 0\pmod n$，其中 $y=O(n^{1/3})$。

我的解法很简单，我们从 $[0,\lfloor n^{1/3}\rfloor]$ 中找到一个 $A\ne 0$，由于 $u$ 接近 $O(n)$ 量级，$Au\bmod n$ 可以看作是随机的，此时期望可以找到一个 $A$，满足 $2Au\bmod n=O(n^{2/3})$（因为相当于 $O(n^{1/3})$ 个随机数里面最小的那个），由于 $y=O(n^{1/3})$，我们期望获得 $3$ 个 $O(n)$ 量级的项 $Ay^2,(2Au\bmod n)y,A(u^2-a)\bmod n$，因此，我们可以枚举 $k$，利用求根公式直接求解二次方程 $Ay^2+(2Au\bmod n)y+A(u^2-a)\bmod n-kn=0$。

因此我们可以写出如下的 python代码：

from math import isqrt,gcd
def f(a,b,c,n):
    a,b=a%c,b%c
    m=(a*n+b)//c
    return min((a*n+b)%c,b,min(a,c)-1+f(-c,b+1-c,-a,m-1)) if a*n*m else min(a*n+b,b)
n,a,b=map(int,[input(),input(),input()])
u=1+isqrt(b**3-1)
Y=isqrt((b+1)**3)-u
G=gcd(2*u,n)
B=f(2*u,2*u-1,n,n//Y//Y)+1
A=B//gcd(B,n)*pow(2*u//G,-1,n//G)%(n//G)
C=(u*u-a)*A%-n
D=B*B-4*A*C
while isqrt(D)**2<D:D+=4*A*n
print(u+(isqrt(D)-B)//A//2)

不出所料拿下最短解。

这里解释一下啊，因为我找到类似于 $A=0$ 或者 $2Au\bmod n=0$ 的解是一点用也没有的，所以我在算最短解的时候实际上算的是 $\max\limits_{i=0}^{\lfloor n/Y^2\rfloor}(2ui+2u-1)\bmod n$ 。

我是先得到 $B=(2Au)\bmod n$ 的，设 $G=\gcd(2u,n)$此时可以用 $(B/\gcd(B,G)\times (2u/G)^{-1})\bmod (n/G)$ 得到 $A$，因为确实很多时候 $n$ 和 $2u$ 不一定互质。

welikestudying的博客

博客

类欧几里得在这里干什么？

SQRT Problem

Comments

Post a comment