P3518 [POI2011]SEJ-Strongbox 题解

· · 题解

码长文不易，点个赞吧。

写在题解之前

不知道这个题为什么这么多伞兵做法。大概是洛谷用的不是官方数据的原因？

建议加强数据/添加官方数据。

题意

很清楚了，略过。

题解

容易列出最基础款的条件：
若可能的密码为 c_1,c_2,...,c_w，则对于 \forall i\in [1,k-1]，\forall t,q_0,q_1,...,q_w，都满足：

t\cdot n+q_0\cdot m_k+q_1\cdot c_1+q_2\cdot c_2+...+q_w\cdot c_w\not = m_i

根据裴蜀定理可知，左式的最小整数值为 \gcd(n,m_k,c_1,c_2,...,c_k)，不妨设其为 g。
也就是说，如果要满足条件，g \nmid m_i。

又因为 n 和 m_k 都是定值，可以挖掘出两个条件。

  2. 若 g 值一定，则 w 的值（即 c 的个数）为 \displaystyle\frac{n}{g}。

一个基本的算法轮廓就出来了，这应该也是洛谷大部分题解的做法。
枚举 \gcd(n,m_k) 的因数作为 g，逐个判断 g 是否整除 m_i。

很遗憾，这个做法的时间复杂度是 O(\sigma(\gcd(n,m_k))\cdot k) 的，其中 \sigma 表示因数个数。因为 \sigma(\gcd(n,m_k) 的值大于 10000，所以不可能过官方数据，但可以过洛谷数据。

我还是写了代码，放在这里。

char calc(ll x) {for(int i=1;i<K;i++) if(m[i]%x==0) return 0;return 1;}
signed main() {
    n=read(),K=read();
    for(int i=1;i<=K;i++) m[i]=read();
    ll i,t=__gcd(n,m[K]);
    for(i=1;i*i<=t;i++) if(t%i==0&&calc(i)) return cout<<n/i<<'\n',0;
    for(--i;i;i--) if(t%i==0&&calc(t/i)) return cout<<n/(t/i)<<'\n',0;
    return 0;
}

考虑怎么优化。

首先，根据定义，有且仅有所有 m_i 的因数不可以作为 g。
所以，我们可以对于每个 m_i' 都枚举因数，用 map 保存不可以作为 g 的数。最后再枚举 g，判断时间降至 O(\log)-O(1)。

可惜，这样复杂度瓶颈转移到了预处理，没有实质性优化。

观察发现，我们将 m_i 和 \gcd(n,m_k) 取 \gcd 后作为新的 m_i'，对答案没有影响。这很显然，因为 g 全都是 \gcd(n,m_k) 的因子。
观察整体性质，容易发现 m_i 中所含的质因子数量在 20 个以内。
所以，不妨预处理出所有可能的质因子，对 m_i 分解质因数时枚举指数即可。这样，时间复杂度会大大降低。

恕我不太会算这个东西的复杂度，但是把 map 换成 unordered_map 即可通过 LOJ 上的官方数据。代码如下。

void dfs(int x,ll s) {
    if(x==pr[0]+1) return mp[s]=1,void();
    for(int i=0;i<=c[x];i++) dfs(x+1,s),s*=pr[x];
}
signed main() {
    n=read(),K=read();
    for(int i=1;i<=K;i++) m[i]=read();
    ll t=__gcd(n,m[K]),tt=t;
    for(int i=1;i<K;i++) v[__gcd(m[i],t)]=1;
    for(ll i=2;i*i<=tt;i++) if(tt%i==0) {
        pr[++pr[0]]=i;while(tt%i==0) tt/=i;}
    if(tt>1) pr[++pr[0]]=tt;
    for(auto y:v) {
        for(int i=1;i<=pr[0];i++) {
            ll w=y.first;c[i]=0;
            while(w%pr[i]==0) ++c[i],w/=pr[i];
        }
        dfs(1,1);
    }
    ll i;for(i=1;i*i<=t;i++) if(t%i==0&&!mp[i]) return cout<<n/i<<'\n',0;
    for(--i;i;i--) if(t%i==0&&!mp[t/i]) return cout<<n/(t/i)<<'\n',0;
    return 0;
}

显然，这个东西还是不太稳。我们考虑时间都去哪了时间多花在了什么上。
对于一个可能的 g，我们仅仅标记它一次就够了。所以如果记忆化 dfs 的话，分解的时间复杂度就会稳定于 O(\sigma(\gcd(n,m_k))。
这样，总共的时间复杂度即为 O(k\cdot \log + \sqrt{\gcd(n,m_k)} + \sigma(\gcd(n,m_k))，瓶颈在于对每个 m_i 求一次 \gcd 上。

代码如下。

void dfs(ll s) {
    if(mp[s]) return;mp[s]=1;
    for(int x=1;x<=pr[0];x++) if(s%pr[x]==0) dfs(s/pr[x]);
}
signed main() {
    n=read(),K=read();
    for(int i=1;i<=K;i++) m[i]=read();
    ll t=__gcd(n,m[K]),tt=t;
    for(int i=1;i<K;i++) v[__gcd(m[i],t)]=1;
    for(ll i=2;i*i<=tt;i++) if(tt%i==0) {
        pr[++pr[0]]=i;while(tt%i==0) tt/=i,++mc[pr[0]];}
    if(tt>1) pr[++pr[0]]=tt,++mc[pr[0]];
    for(auto y:v) dfs(y.first);
    ll i;for(i=1;i*i<=t;i++) if(t%i==0&&!mp[i]) return cout<<n/i<<'\n',0;
    for(--i;i;i--) if(t%i==0&&!mp[t/i]) return cout<<n/(t/i)<<'\n',0;
    return 0;
}