1 条题解

  • 6
    @ 2023-3-11 18:32:22

    说句闲话,这个 idea 是我在去年暑假的一天里梦见的。

    看到我们只能询问离散对数方程的解,不难想到原根。因为原根有一个很好的性质:在模 pp 意义下,若 ggpp 的原根,1a<p,gxa(modp)\forall 1 \leq a < p, g^x \equiv a \pmod p 是一定有解的。

    但题目没有给我们 pp 的原根,考虑猜出原根 gg。如果直接从 11 开始枚举 gg 并判断,最坏情况下最小的 ggO(p14)O(p^{\frac{1}{4}}) 的,无法通过所有数据。但注意到对于质数 pp,其原根个数为 φ(φ(p))\varphi(\varphi(p)),这个数字大概在 p3p2\frac{p}{3} \sim \frac{p}{2} 之间,也就是说,我们期望 33 次左右就能随机出一个 pp 的原根。

    现在考虑判断一个数 g0g_0 是否为 pp 的原根。首先我们通过 g0x0(modp)g_0^x \equiv 0 \pmod p 判掉 g0g_0pp 的倍数的情况。尽管我们不能知道 pp 是什么,但注意到上面提到的原根的性质,我们可以随机若干正整数 ss,仍然先判掉 sspp 的倍数的情况,然后看 g0xs(modp)g_0^x \equiv s \pmod p 是否有解,如果无解,则 g0g_0 不为 pp 的原根。考虑到所有非 pp 的原根的 g0g_0 都存在一个 tt,使 g0gt(modp)g_0 \equiv g^t \pmod pgcd(t,φ(p))>1\gcd(t, \varphi(p)) > 1,当 utx(modφ(p))ut \equiv x \pmod{\varphi(p)} 无解即 gcd(t,φ(p))∤x\gcd(t, \varphi(p)) \not\mid x 时可以判定 g0g_0 不为 pp 的原根。也就是说,假如无解,我们期望 22 次左右随机出一个足以判定 g0g_0 不满足条件的 ss。为了保险,这里我们可以取 1010 次。

    求完原根后,我们来构造方程。由于题目允许我们对非常大的 a,ba, b 做出询问(不超过 101.8×101910^{1.8 \times 10^{19}} 量级),考虑随机一个 x0x_0,令 F(x)=xF(x) = xG(x)=xx0G(x) = x^{x_0}u=v=gu = v = g。由于 pp 为质数,根据欧拉定理,我们有 x0x(modφ(p))x_0 \equiv x \pmod{\varphi(p)},进而可以得到 φ(p)(x0x)\varphi(p) \mid (x_0 - x)

    于是我们把询问次数卡满,对每次得到的 x0xx_0 - xgcd\gcd,将最终所得的值 +1+ 1 即可得到 pp。这样看上去很不靠谱,但实际上极大概率可以得到一个合法的解,因为我们可以将 x0modφ(p)x_0 \bmod \varphi(p) 视为一个随机数且存在下面这个结论:

    • 两个 O(n)O(n) 级别的随机数的 gcd\gcd 的期望大小是 O(lnn)O(\ln n) 的。

    证明:$O(\dfrac{\displaystyle\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i, j)}{n^2}) = O(\dfrac{\displaystyle\sum_{d = 1}^n \varphi(d) \lfloor \frac{n}{d} \rfloor^2}{n^2}) = O(\displaystyle\sum_{d = 1}^n \frac{\varphi(d)}{d^2}) \leq O(\displaystyle\sum_{d = 1}^n \frac{1}{d}) = O(\ln n)$。

    于是我们只需要询问期望 O(lnwp)O(\ln^* \frac{w}{p})w=1018w = 10^{18})次即期望 44 次左右就可以得到 pp 的值。当然因为两边值域不一定对称,实测在保证可以得到答案的前提下需要 1515 次。

    最终我们只需要期望 7070 次左右的询问即可得到答案,实测在保证可以得到答案的前提下一般需要 508050 \sim 80 次左右,最大需要 100100 次左右。

    代码:

    #include <iostream>
    #include <vector>
    #include <iostream>
    #include <vector>
    #include <random>
    #include <ctime>
    
    using namespace std;
    
    typedef long long ll;
    
    const int N = 50 + 7;
    const ll M = 1e18;
    int t, cnt = 0;
    ll bucket[N];
    mt19937 e(time(NULL));
    uniform_int_distribution<ll> rnd(1, M);
    
    inline ll ask(int n, int m, ll u, ll v, vector<ll> c, vector<ll> d, vector<ll> e, vector<ll> f){
    	ll ans = 0;
    	cout << "ask " << n << " " << m << " " << u << " " << v << "\n";
    	for (register int i = 0; i < n; i++){
    		cout << c[i] << " ";
    	}
    	cout << "\n";
    	for (register int i = 0; i < m; i++){
    		cout << d[i] << " ";
    	}
    	cout << "\n";
    	for (register int i = 0; i < n; i++){
    		cout << e[i] << " ";
    	}
    	cout << "\n";
    	for (register int i = 0; i < m; i++){
    		cout << f[i] << " ";
    	}
    	cout << endl;
    	cin >> ans;
    	return ans;
    }
    
    inline ll make(){
    	ll ans;
    	do {
    		ans = rnd(e);
    		t--;
    	} while (ask(1, 1, ans, 0, vector<ll>{1}, vector<ll>{0}, vector<ll>{1}, vector<ll>{0}) != -1);
    	return bucket[++cnt] = ans;
    }
    
    ll gcd(ll a, ll b){
    	return b == 0 ? a : gcd(b, a % b);
    }
    
    inline void answer(ll p_){
    	cout << "answer " << p_ << endl;
    }
    
    int main(){
    	ll g, phi_p = 0;
    	cin >> t;
    	while (true){
    		int pos = 1;
    		bool flag = true;
    		g = make();
    		for (register int i = 1; i <= 10; i++){
    			if (pos > cnt){
    				make();
    			} else if (bucket[pos] == g){
    				pos++;
    				if (pos > cnt) make();
    			}
    			t--;
    			if (ask(1, 1, g, bucket[pos], vector<ll>{1}, vector<ll>{1}, vector<ll>{1}, vector<ll>{1}) == -1){
    				flag = false;
    				break;
    			}
    			pos++;
    		}
    		if (flag) break;
    	}
    	while (--t >= 0){
    		ll x0 = rnd(e), x = ask(1, 1, g, g, vector<ll>{1}, vector<ll>{x0}, vector<ll>{1}, vector<ll>{1});
    		phi_p = gcd(phi_p, x0 - x);
    	}
    	answer(phi_p + 1);
    	return 0;
    }
    
    • 1

    信息

    ID
    278
    时间
    2000ms
    内存
    512MiB
    难度
    8
    标签
    递交数
    35
    已通过
    14
    上传者