题解：P10383 「HOI R1」杂分选约

· · 题解

更好的阅读体验

学生零太强大了。

考虑到题目保证了 p, q \le 3 \times 10^9。记值域 V = 3 \times 10^9。

则我们声称，取一个大质数 P > V^2，然后求出 \left(\prod \limits_{i = 1}^n a_i\right)\left(\prod \limits_{i = 1}^m b_i\right)^{-1} \equiv x \pmod {P}。则如果找到了 x \cdot y^{-1} \equiv x \pmod {P}，则我们求得的 x, y 就是最终的答案。

由定义 \frac{p}{q} \equiv \frac{x}{y} \pmod {P}。

那么 py \equiv qx \pmod {P}，即 py - qx = kP, k \isin \N。

显然 py - qx < V^2, kP > V^2，因此 py - qx = 0，即 \frac{p}{q} = \frac{x}{y}。

现在要解同余方程 \frac{p}{q} \equiv x \pmod {P}。可以转化为 p \equiv qx \pmod {P}。

那么可以 BSGS。设一个阈值 B，假设 q = aB + b，那么 p \equiv aBx + bx \pmod {P}。我们接下来先枚举 a，将 aBx 使用一个数据结构存下来。

接下来我们枚举 b，想要知道对于这个 b 有没有满足条件的 a。然后由于 aBx < 2P，所以 aBx + bx \isin [0, V] 或 [P, P+V]，也就是查询是否存在 [0, V - bx] \cup [P - bx, P + V - bx] 的范围内是否存在我们已经存好的 aBx。

我们可以把 aBx 排序一下，然后在上面二分，就可以得到是否有在给定范围内的 aBx 了。

那么这道题就做完了，理论上 B = \sqrt V，复杂度可以到达 O(n + \sqrt V \log V)。实际上 B = 10^4 较快。

要卡常，快读是贺 Purslane 的。

#include<bits/stdc++.h>
#define endl '\n'
#define N 1000006
using namespace std;
using i64=long long;
using i128=__int128;
constexpr i128 MOD=(i128)9000000000000000041;
constexpr int B=1e4,iB=3e5;
int n,m,_,tot;
i128 t,ma=1,mb=1,val,ival,num[iB+6];
inline void write(i128 k)
{
    if(k<0)putchar('-'),k=-k;
    int nnum[40],ttp=0;
    while(k)nnum[++ttp]=k%10,k/=10;
    if(!ttp)nnum[++ttp]=0;
    while(ttp)putchar(nnum[ttp--]^48);
}
class IO_helper{ // by purslane
private:
    static const int L = 1 << 16;
    char in_buf[L], *in_st, *out_st;

    char _getc(){
        if (in_st == out_st)
        {
            out_st = (in_st = in_buf) + fread(in_buf, 1, L, stdin);
            if (in_st == out_st) return EOF;
        }
        return *in_st++;
    }
public:
    template <typename IntType>
    IO_helper &operator>>(IntType &x){
        bool ok=0;
        char c; while ((c = _getc()) < '0' || c > '9')ok|=c=='-';
        for (x = 0; c >= '0' && c <= '9'; c = _getc())
            x = x * 10 + c - '0';
        x=(ok?-x:x);
        return *this;
    }
} IO;
i128 qpow(i128 x,i128 y=MOD-2)
{
    i128 ret=1;
    for(;y;y>>=1,x=x*x%MOD)if(y&1)ret=ret*x%MOD;
    return ret;
}
i128 gcd128(i128 x,i128 y) {return y?gcd128(y,x%y):x;}
int check(i128 p)
{
    i128 q=ival*p%MOD;
    if(p&&q&&p<=3e9&&q<=3e9)
    {
        i128 g=gcd128(p,q);
        p/=g,q/=g,write(p),putchar(32),write(q),putchar(10);
        return 1;
    }
    return 0;
}
int lb(i128 x)
{
    int l=1,r=tot,ret=tot+1;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(num[mid]>x)ret=mid,r=mid-1;
        else l=mid+1;
    }
    return ret;
}
main()
{
    IO>>n>>m>>_;
    for(int i=1;i<=n;i++)IO>>t,ma=ma*t%MOD;
    for(int i=1;i<=m;i++)IO>>t,mb=mb*t%MOD;
    val=ma*qpow(mb)%MOD,ival=qpow(val);
    for(int i=0;i<iB;i++)num[++tot]=i*B*val%MOD;
    sort(num+1,num+1+tot);
    for(int i=0,it;i<B;i++)
    {
        i128 b=(MOD-i*val%MOD)%MOD;
        it=lb(b);
        if(it<=tot&&check((i*val+num[it])%MOD))return 0;
        it=lb(0);
        if(it<=tot&&check((i*val+num[it])%MOD))return 0;
    }
    write(val),printf(" 1\n");
    return 0;
}