CF-1027-F. Small Operations（通过选择1-K内的整数*和/使X==Y）

思路讲解

首先，遇到数论问题不要怕，我们人类其实对许多数论问题其实都束手无策，就靠计算机枚举。

那么，通过素因数分解，不难发现，我们可以把问题转化为这个。

💡 Note: 给你一个序列，比如说1，2，2，3，5，你要将这个序列删空，你一次可以选择任意多的数，只要这些数的乘积小于K。要求你找到一个方式，使用最少删除次数，告诉我这个次数。

那么其实经过素因数分解得出的序列是不会有 1 的。

把xrem除掉，再乘上yrem，就相等了。

---

记忆化搜索的时间复杂度那基本上等于 $状态数\times入口数量$，这里的状态数量其实就是因数的数量，入口数量也是因数数量，所以最坏情况下时间复杂度为 $O(n^{\frac{2}{3}})$。

这个super composite number 就是因数数量特别多的数，比比他小的所有数的因数都多，那么这样的数大概因数数量也就是 $\sqrt[3]{n}$ 。

A highly composite number is a positive integer that has more divisors than all smaller positive integers. If d(n) denotes the number of divisors of a positive integer n, then a positive integer N is highly composite if d(N) > d(n) for all n < N. For example, 6 is highly composite because d(6)=4, and for n=1,2,3,4,5, you get d(n)=1,2,2,3,2, respectively, which are all less than 4.

ll dfs(ll val){
	if(dp[val]!=INF) return dp[val]+1;
	if(val==1) return 1;
	FOR(i,0,SZ(facs)-1){
		ll fac=facs[i];
		if(fac==1) continue;
		if(fac>K) break;
		if(val%fac==0) dp[val]=min(dp[val],dfs(val/fac));
	}
	return dp[val]+1;
}

那么问题的关键就在于减少入口，注意到只有因数是合法的。

AC代码

https://codeforces.com/contest/2114/submission/323597405

源代码

// Problem: F. Small Operations
// Contest: Codeforces - Codeforces Round 1027 (Div. 3)
// URL: https://codeforces.com/contest/2114/problem/F
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,Y,K,lT,A[MAXN];
/*

*/
inline ll gcd(ll a,ll b){
	if(a<b) swap(a,b);
	while(b){
		a%=b;
		swap(a,b);
	}
	return a;
}
namespace F{
	inline vector<ll> de(ll n){
		vector<ll> ret;
		for(ll i=1;i*i<=n;++i){
			if(n%i==0){
// #ifdef LOCAL
    // debug(i);
    // debug(n/i);
// #endif
				if(i!=1) ret.pb(i);
				if(i*i!=n) ret.pb(n/i);
// #ifdef LOCAL
    // FOR(i,0,SZ(ret)-1) debug(ret[i]);
// #endif
			}
		}
		sort(all(ret));
		return ret;
	}
};
namespace P{		// 质因数分解   时间复杂度sqrt(n)
	// AC https://www.luogu.com.cn/record/219974780
	typedef array<ll,2> arr2;
	
	inline vector<arr2>  de(ll n){		// 主函数
		if(n==1) return {{1,1}};	// 确保无论什么输入都不会返回空值
		vector<arr2> prime;
		ll opN=n;
		for(ll i=2;i*i<=n;++i){
			if(opN==1) break;
			ll cnt=0;
			while(opN%i==0 && opN!=1){
				opN/=i;
				++cnt;
			}
			if(cnt==0) continue;
			prime.pb({i,cnt});
		}
		if(opN!=1) prime.pb({opN,1});	// 素因子可能大于sqrt(n)，比如23，包括20的5
		return prime;
	}
	inline void print(const vector<arr2> &prime){	// 20 -> 2^2 * 5
		FOR(i,0,SZ(prime)-1){
			if(i==0){
				if(prime[i][1]==1) cout<<prime[i][0]<<" ";
				else cout<<prime[i][0]<<"^"<<prime[i][1]<<" ";
			}else{
				if(prime[i][1]==1) cout<<"* "<<prime[i][0]<<" ";
				else cout<<"* "<<prime[i][0]<<"^"<<prime[i][1]<<" ";
			}
		}
	}
}
ll dp[MAXN];
vector<ll> facs;
vector<arr2> primes;
ll dfs(ll val){
	if(dp[val]!=INF) return dp[val]+1;
	if(val==1) return 1;
	FOR(i,0,SZ(facs)-1){
		ll fac=facs[i];
		if(fac==1) continue;
		if(fac>K) break;
		if(val%fac==0) dp[val]=min(dp[val],dfs(val/fac));
	}
	return dp[val]+1;
}

inline void init(ll n){
	FOR(i,0,SZ(facs)-1){dp[facs[i]]=INF;}
	dp[1]=0;
}
inline void solve(){
	cin>>X>>Y>>K;
	ll gxy=gcd(X,Y);
	ll xrem=X/gxy,yrem=Y/gxy;
	
	facs=F::de(xrem);
	init(xrem);
	primes=P::de(xrem);
	if(primes.back()[0]>K){
		cout<<-1<<"\n";
		return;
	}
// #ifdef LOCAL
    // cerr << "OK:"<<lT << '\n';
    // debug(xrem);
    // debug(K);
    // FOR(i,0,SZ(facs)-1) debug(facs[i]);
// #endif
	dfs(xrem);
// #ifdef LOCAL
    // cerr << "OK1:"<<lT << '\n';
// #endif
	ll ans=dp[xrem];
	
#ifdef LOCAL
	cerr<<"init:\n";
     FOR(i,0,SZ(facs)-1) {debug(facs[i]);debug(dp[facs[i]]);}
#endif
	facs=F::de(yrem);
	init(yrem);
	primes=P::de(yrem);
	if(primes.back()[0]>K){
		cout<<-1<<"\n";
		return;
	}
	dfs(yrem);
#ifdef LOCAL
    cerr << "OK2:"<<lT << '\n';
    FOR(i,0,SZ(facs)-1) {debug(facs[i]);debug(dp[facs[i]]);}
    // FOR(i,1,N){
    	// debug(i);
    // }
#endif
	ans+=dp[yrem];
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC https://codeforces.com/contest/2114/submission/323597405
*/

心路历程（WA，TLE，MLE……）