原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ375.html

题解

首先，我们可以建出一个 k 个点的自动机，第 i 个点表示当前数对 k 取模为 i-1。显然每一个点有 m-1 条出边。

然后，稍加观察，我们就可以发现，如果一些节点的出边集合是相同的，我们就可以将他们合并。

具体是怎样的节点呢？

对于每一个 $t$ ，满足

$$im \equiv t\pmod k $$

的所有 $i$ 都可以合并（节点 0 除外）。

然后你就发现你几乎过了大样例的前 100 个数据。

只有很少是错的。

所以大概会得到0分的好成绩。

那么错在了哪儿？

并不是这样合并完了就没有节点可以合并了。

我们再想想哪些节点可以合并。

注意到如果 $im^2\equiv jm^2\pmod k $ 的话，只要在后面接上两个字母，$i$ 和 $j$ 就没区别了。

但是如果其中一个走一步就可以到 0 了，另一个不行，那么他们就是不等价的。

除此之外的情况都可以合并。

类似地，对于 $m^3,m^4,m^5,\cdots$ 也差不多。

于是我们就可以得到一个 $O(k\log ^2 k)$ 的模拟。

可以获得 50 分的好成绩。

再看看质数的情况，由于当 $\gcd(k,m)=1$ 时，答案等于 $k$ ，所以 $k$ 一定是 $m$ 的倍数。稍微模拟一下可以发现，一次合并之后相当于缩小了问题规模，而去求 $k'=k/m,m'=m$ 的子问题。简单推导一下就可以得到质数的10分。

现在已经得到了 60 分的好成绩。

现在我们来看看 60 分的做法给了我们什么启发：缩小问题规模。

设 $d = \gcd(k,m)>1$ ，则一开始给 $1\cdots k-1$ （0是特殊点被ban掉了）乘了 m 模了 k 之后，所有数都是 d 的倍数。

设 $t=\frac kd$ ，则 $1\cdots k-1$ 乘m模k 后的结果是 $t$ 个一循环的，所以 d 的每一个倍数都会出现。我们把每一种乘m模k相同的缩起来显然是最优的，那么，我们可以合并 $(k-1) - t$ 次。

现在还剩下 $t$ 个节点，注意到现在加上 $0\cdots m-1$ 之后与 k 同余的节点显然不能参与下一次合并，所以我们要把他们扔掉。

扔掉的是那些呢？

好像有点棘手。我们先绕个弯。之前说道这里的所有数都是 d 的倍数。所以我们把所有值都除以 d，k' = k/d, m'=m/d 。由于之前提到 " d 的每一个倍数都会出现"，所以所有值除以 d 之后，得到的就是 $1,2,\cdots , k'-1$ 。我们扔掉后 $m'$ 个数，所以剩下的就是 $1,2,\cdots ,k'-m$ 。

我们发现我们得到了一个原问题的子问题。

于是我们可以考虑把这种问题一般化：

假设读入的两个数第一个是 n ，第二个是 k 。

假设当前剩余节点 $1,2,\cdots ub$ ，$m$ 为 $n$ 的若干次幂除以一些 gcd ，$k$ 表示除过一些 gcd 的 k ，在这种状态下，我们来计算最多可以合并多少节点。初始情况下， ub = k - 1, m = 1, k = k 。

令 $d = \gcd(k,n),t=k/d$ ，

考虑分几种情况讨论：

1. d = 1：显然不能合并。

2. $ub\leq t$：乘以 m 之后的得到的结果互不相同，所以也不能合并。

3. 这种情况下可以合并 $ub - t$ 次。合并完之后，显然还剩 $t$ 个点。这时候 $m' = m\cdot (n/d)$，扔掉 $m'$ 个点之后还剩 $t-m'$ 个，所以 $ub' = t - m'$ ，剩下就是 $k' = t$ 。

注意一下运算的时候不要爆 long long 。

于是你就可以得到 100 分的好成绩。

代码1 - 60分

#include <bits/stdc++.h>

#define clr(x) memset(x,0,sizeof (x))

#define For(i,a,b) for (int i=a;i<=b;i++)

#define Fod(i,b,a) for (int i=b;i>=a;i--)

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define _SEED_ ('C'+'L'+'Y'+'A'+'K'+'I'+'O'+'I')

#define outval(x) printf(#x" = %d\n",x)

#define outvec(x) printf("vec "#x" = ");for (auto _v : x)printf("%d ",_v);puts("")

#define outtag(x) puts("----------"#x"----------")

using namespace std;

typedef long long LL;

LL read(){

	LL x=0,f=0;

	char ch=getchar();

	while (!isdigit(ch))

		f|=ch=='-',ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return f?-x:x;

}

LL T,n,k;

LL gcd(LL a,LL b){

	return b?gcd(b,a%b):a;

}

vector <int> v;

int tn(int x){

	return x?x:k;

}

int main(){

	T=read();

	while (T--){

		n=read(),k=read();

		if (gcd(n,k)==1){

			printf("%lld\n",k);

			continue;

		}

		if (n>1e5||k>1e5){

			LL ans=k,c=0;

			while (ans%n==0)

				ans/=n,c++;

			printf("%lld\n",ans+c);

			continue;

		}

		LL m=1,ans=k;

		v.clear();

		For(i,0,k-1)

			v.pb(tn(i));

		while (1){

			sort(v.begin(),v.end());

//			outvec(v);

			if (v.empty())

				break;

			int cnt=unique(v.begin(),v.end())-v.begin();

			while (v.size()>cnt)

				v.pop_back(),ans--;

//			outvec(v);

			while (!v.empty()&&v.back()>k-m)

				v.pop_back();

//			outvec(v);

			for (auto &i : v)

				i=tn(i*n%k);

			if (k/m==0)

				break;

			m*=n;

		}

		cout<<ans<<endl;

	}

	return 0;

}

代码2 - 100分

#include <bits/stdc++.h>

#define clr(x) memset(x,0,sizeof (x))

#define For(i,a,b) for (int i=a;i<=b;i++)

#define Fod(i,b,a) for (int i=b;i>=a;i--)

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define _SEED_ ('C'+'L'+'Y'+'A'+'K'+'I'+'O'+'I')

#define outval(x) printf(#x" = %d\n",x)

#define outvec(x) printf("vec "#x" = ");for (auto _v : x)printf("%d ",_v);puts("")

#define outtag(x) puts("----------"#x"----------")

using namespace std;

typedef long long LL;

LL read(){

	LL x=0,f=0;

	char ch=getchar();

	while (!isdigit(ch))

		f|=ch=='-',ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return f?-x:x;

}

LL T,n,k;

LL gcd(LL a,LL b){

	return b?gcd(b,a%b):a;

}

int main(){

	T=read();

	while (T--){

		n=read(),k=read();

		LL ans=k,ub=k-1,m=1;

		while (ub>0){

			LL d=gcd(k,n),t=k/d;

			if (d==1||ub<=t)

				break;

			ans-=ub-t;

			if (t/m/(n/d)==0)

				break;

			m*=n/d;

			ub=t-m;

			k/=d;

		}

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

UOJ#375. 【ZJOI2018】迷宫

题解

代码1 - 60分

代码2 - 100分

最新文章

热门文章