CF-1027-F. Small Operations（通过选择1-K内的整数*和/使X==Y） · znzryb
## 思路讲解
首先，遇到数论问题不要怕，我们人类其实对许多数论问题其实都束手无策，就靠计算机枚举。
那么，通过素因数分解，不难发现，我们可以把问题转化为这个。
> 💡 **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](https://en.wikipedia.org/wiki/Positive_integer) that has more [divisors](https://en.wikipedia.org/wiki/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.
```cpp
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](https://codeforces.com/contest/2114/submission/323597405)
::: 源代码
```cpp
// 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……）