题解：CF2114F Small Operations

题目描述

给你两个正整数

x,k

。进行以下两种变换之一称为一次操作：

选择一个满足 $1 \le a \le k$ 的正整数 $a$ ，使 $x$ 变为 $x\cdot a$ ；
选择一个满足 $1 \le a \le k$ 的正整数 $a$ ，使 $x$ 变为 $\frac{x}{a}$ ，要求操作完后 $x$ 值是整数。

你需要找出使

x

变为给定正整数

y

的最小操作次数，或判断无解。

Sol

考虑先将

x

变为

\gcd(x,y)

再将

\gcd(x,y)

变为

y

。显然这样操作所需的次数最少。

先将

\frac{x}{\gcd(x,y)}

和

\frac{y}{\gcd(x,y)}

因数分解，再用 dp 将其凑起来就行。

设

dp_i

为当前因数的乘积为

i

是所需的最小操作次数，

dp

的过程就用记忆化搜索就行了。

\large dp_i=\max (dp_i,dp_\frac{i}{d(i)} +1)

其中

d(i)

为小于

k

的

i

的因数。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
int dp[1000005];
bool check(int x,int k){
	for (int i=2;i*i<=x&&i<=k;i++) while (x%i==0) x/=i;
	return (x<=k);
}

int dfs(int x,int k){
	if(x==1) return 0;
	if(dp[x]) return dp[x];
	if(x<=k){
		dp[x]=1;
		return 1;
	}
	dp[x]=1e9;
	for(int i=k;i>1;i--) if(x%i==0) dp[x]=min(dp[x],dfs(x/i,k)+1);
	return dp[x];
}



int main(){
	int T;
	cin>>T;
	while(T--){
		memset(dp,0,sizeof dp);
		int a,b,k,ans=0;
		cin>>a>>b>>k;
		int fk=__gcd(a,b);
		a=a/fk,b=b/fk;
		if(!check(a,k) || !check(b,k)){
			cout<<-1<<endl;
			continue; 
		}
		cout<<dfs(a,k)+dfs(b,k)<<endl;
	}
}

题解：CF2114F Small Operations

文章操作

题目描述

Sol

Code

相关推荐

评论

题解：CF2114F Small Operations