自动搬运

查看原文

来自洛谷，原作者为

	KaisuoShutong 我想说别走 却没有借口。

搬运于2025-08-24 21:49:45，当前版本为作者最后更新于2021-08-06 11:29:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

码长文不易，点个赞吧。

写在题解之前

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

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

题意

很清楚了，略过。

题解

容易列出最基础款的条件：
若可能的密码为 $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$ 都是定值，可以挖掘出两个条件。

1. $g \mid \gcd(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;
}