CF2114F

题解

注意到最好的方案是将

a

通过操作转化为

\gcd(a,b)

再将其转化为

b

。

证：若转化到低于

\gcd(a,b)

的数，下一步最优肯定要转化到

b

的因数。由于有

k

的限制，所以在合法方案下，在

\gcd(a,b)

上可以一步转化到的一个数

x

，在低于

\gcd(a,b)

上需要至少一次操作转化到

x

。因此从

\gcd(a,b)

转化不劣。

然后设

x=\frac{a}{\gcd(a,b)}

，

y=\frac{b}{\gcd(a,b)}

，此时

\gcd(x,y)=1

，问题转化为将

x

变为

1

再变为

y

的最小操作次数。

可以看作将

x

除到

1

加上将

y

除到

1

的操作次数，前提为除数小于等于

k

。

发现如果

x

和

y

中有任意一个，它的最大质因数大于

k

，则无解。

其余情况皆有解，用记忆化搜索即可。

用 memset 炸了，考试慎用 memset。

代码

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int _;
ll x,y,k;
ll f[N];
inline ll dfs(ll x) {
	if(x==1) return 0;
	if(x<=k) return 1;
	if(f[x]!=-1) return f[x];
	for(int i=k;i>1;i--) {
		if(x%i==0) {
			ll nxt=dfs(x/i);
			if(nxt==-1) continue;
			if(f[x]==-1) f[x]=nxt+1ll;
			else f[x]=min(f[x],nxt+1ll);
		}
	}
	return f[x];
}
inline ll gcd(ll a,ll b) {
	if(!b) return a;
	return gcd(b,a%b);
}
int main() {
	scanf("%d",&_);
	while(_--) {
		scanf("%lld%lld%lld",&x,&y,&k);
		ll g=gcd(x,y);
		ll a=x/g,b=y/g;
		for(int i=1;i<=max(a,b);i++) f[i]=-1;
		if(dfs(a)==-1||dfs(b)==-1) puts("-1");
		else printf("%lld\n",dfs(a)+dfs(b));
	}
	return 0;
}

文章操作

题解

代码

相关推荐

评论

CF2114F