Znzryb's Blog

CF-1026-D. Fewer Batteries

Posted on 2025-06-11 Edited on 2026-02-17

思路讲解

检查点之间共有 $m$ 条单向通道。第 $i$ 条通道允许从点 $s_i$ 移动到点 $t_i$ （ $s_i < t_i$ ），但不允许反方向移动。此外，只有当机器人至少拥有 $w_i$ 个充电电池时，才能使用第 $i$ 条通道；否则，它将在途中耗尽电量。

这个 $s_i < t_i$ 尤为关键，这说明了这张图是有向无环图（DAG）。

那么二分做法不用多说，使用天然的拓扑排序以及类似dp做法解决，然后注意斜体加粗部分。

inline bool check(ll mid){
	FOR(i,0,N+5){Mxb[i]=0;}
	FOR(i,1,N){
		if(i!=1 && Mxb[i]==0) continue;
		FOR(j,0,SZ(g[i])-1){
			ll v=g[i][j][0],w=g[i][j][1];
			if(min(mid,Mxb[i]+B[i])>=w){
				Mxb[v]=max(Mxb[v],Mxb[i]+B[i]);
				Mxb[v]=min(Mxb[v],mid);
			}
		}
	}
	if(Mxb[N]==0) return false;
	return true;
}

AC代码

https://codeforces.com/contest/2110/submission/324044393

源代码

// Problem: D. Fewer Batteries  D. 更少的电池
// Contest: Codeforces - Codeforces Round 1026 (Div. 2)Codeforces 第 1026 轮（第 2 组）
// URL: https://codeforces.com/contest/2110/problem/D
// 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,K,lT,B[MAXN];
vector<arr2> g[MAXN];		// 记得要清空
ll Mxb[MAXN];
// bitset<MAXN> vis;
/*

*/
inline void init(){
	FOR(i,0,N+5){g[i].clear();}
}
inline bool check(ll mid){
	FOR(i,0,N+5){Mxb[i]=0;}
	FOR(i,1,N){
		if(i!=1 && Mxb[i]==0) continue;
		FOR(j,0,SZ(g[i])-1){
			ll v=g[i][j][0],w=g[i][j][1];
// #ifdef LOCAL
    // if(w==10){
    	// debug(Mxb[i]+B[i]);
    // }
// #endif
			if(min(mid,Mxb[i]+B[i])>=w){
				Mxb[v]=max(Mxb[v],Mxb[i]+B[i]);
				Mxb[v]=min(Mxb[v],mid);
			}
			// assert(Mxb[i]+B[i]>=w);
		}
	}
#ifdef LOCAL
	debug(mid);
    FOR(i,1,N){debug(i);debug(Mxb[i]);}
    cerr<<"\n";
#endif
	if(Mxb[N]==0) return false;
	return true;
}
inline void solve(){
	cin>>N>>M;
	init();
	FOR(i,1,N){
		cin>>B[i];
	}
	ll mxw=0;
	FOR(i,1,M){
		ll u,v,w;
		cin>>u>>v>>w;
		// 把g反过来
		// g[v].pb({u,w});
		g[u].pb({v,w});
		mxw=max(mxw,w);
	}
	ll l=1;ll r=mxw;
	if(!check(r)){cout<<-1<<"\n";return;}
	while(l<r){
		ll mid=l+r>>1;
		if(check(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l<<"\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/2110/submission/324044393
*/

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

TLE，该代码一个点被访问多次，那么其所有边都将重新遍历一次。

源代码

// Problem: D. Fewer Batteries  D. 更少的电池
// Contest: Codeforces - Codeforces Round 1026 (Div. 2)Codeforces 第 1026 轮（第 2 组）
// URL: https://codeforces.com/contest/2110/problem/D
// 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,K,lT,B[MAXN];
vector<arr2> g[MAXN];		// 记得要清空
ll Mx[MAXN];
bitset<MAXN> vis;
/*

*/
inline void init(){
	FOR(i,0,N+5){vis[i]=false;Mx[i]=INF;g[i].clear();}
}
void dfs(ll node,ll mx,ll ba){
	// vis[node]=true;
#ifdef LOCAL
    debug(node);
    debug(mx);
    debug(ba);
    cerr<<"\n";
#endif
	Mx[node]=min(Mx[node],mx);
	ba+=B[node];
	FOR(i,0,SZ(g[node])-1){
		ll lnode=g[node][i][0],w=g[node][i][1];
		// if(vis[lnode]) continue;
		if(ba<w) continue;
		dfs(lnode,max(mx,w),ba);
	}
}
inline void solve(){
	cin>>N>>M;
	init();
	FOR(i,1,N){
		cin>>B[i];
	}
	FOR(i,1,M){
		ll u,v,w;
		cin>>u>>v>>w;
		// 把g反过来
		// g[v].pb({u,w});
		g[u].pb({v,w});
	}
	dfs(1,0,0);
	// dfsn(N,0);
	if(Mx[N]==INF){	// 未联通
		cout<<-1<<"\n";
		return;
	}
	cout<<Mx[N]<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/

CF-1026-C. Racing （让无人机上升还是保持不变以通过障碍）

Posted on 2025-06-11 Edited on 2026-02-17

思路讲解

题目总结

这是一道关于无人机通过障碍门的问题。有 N 道门，每道门都有高度范围 [l_i, r_i]。无人机初始高度为 0，每次可以选择保持高度不变或上升 1 个单位。部分门的操作已经固定（0 表示保持不变，1 表示上升），部分门的操作待定（-1 表示可以自由选择）。需要判断是否存在合法方案使无人机能通过所有门，如果存在则输出一种方案，否则输出 -1。

虽然这种题不是不可能dp，但dp不太可能。

容易想到一种贪心，在每一道门前尽量增加高度，

但是要注意这个高度的上界是什么。

// 在每一道门前尽量增加高度，但是要注意这个高度的上界是什么
ROF(i,N,1){
	ll r=lr[i][1];
	if(D[i]==1){	
	// 这里-1是因为这里当然不会判断，但是当mnR[i-1]来读这个mnR[i]的时候
	// 我们希望mnR[i-1]的上界不能是mnR[i]，因为+1就超了
	// 连续操作与传递同理
		mnR[i]=min(r-1,mnR[i+1]-1);
	}else{
		mnR[i]=min(r,mnR[i+1]);
	}
}

这个上界不仅会受到后续最小 r 的影响，还会收到固定操作的影响

AC代码

https://codeforces.com/contest/2110/submission/323871174

源代码

// Problem: C. Racing
// Contest: Codeforces - Codeforces Round 1026 (Div. 2)
// URL: https://codeforces.com/contest/2110/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 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,K,lT,D[MAXN];
arr2 lr[MAXN];
ll mnR[MAXN];
/*

*/
inline void init(){
	FOR(i,0,N+5){mnR[i]=INF;}
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){cin>>D[i];}
	FOR(i,1,N){
		ll l,r;cin>>l>>r;
		lr[i]={l,r};
	}
	// li>rj  i<j 时必定无解。
	ll mxl=0;
	FOR(i,1,N){
		ll l=lr[i][0],r=lr[i][1];
		if(r<mxl){
			cout<<-1<<"\n";
			return;
		}
		mxl=max(l,mxl);
	}
	// 在每一道门前尽量增加高度，但是要注意这个高度的上界是什么
	ROF(i,N,1){
		ll r=lr[i][1];
		if(D[i]==1){
			mnR[i]=min(r-1,mnR[i+1]-1);
		}else{
			mnR[i]=min(r,mnR[i+1]);
		}
	}
	ll cnt1=0,curh=0;
	FOR(i,1,N){
		ll l=lr[i][0],r=lr[i][1];
		if(D[i]==0){
			if(curh<l || curh>r){
				cout<<-1<<"\n";
				return;
			}
		}else if(D[i]==1){
			curh+=1;
			if(curh<l || curh>r){
				cout<<-1<<"\n";
				return;
			}
		}else{
			if(curh+1<=mnR[i]){
				curh+=1;
				D[i]=1;
			}else{
				D[i]=0;
			}
			if(curh<l || curh>r){
				cout<<-1<<"\n";
				return;
			}
		}
	}
	FOR(i,1,N){cout<<D[i]<<" ";}
	cout<<"\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/2110/submission/323871174
*/

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

CF-1029-G. Omg Graph（路径成本定义为最短边和最长边之和）

Posted on 2025-06-10 Edited on 2026-02-17

思路讲解

注意到呢，把边固定下来，然后这个时候就只要去看简单路径了。因为走越多，遇到大的边的可能性越大。

当然，我们的下一步推进遇到了问题，这个问题不是树上问题，m 没有限定，那么 dp 就废了。

不过问题不大，容易想到如果不是树，我们能不能把它变为树？用最小生成树。

AC代码

https://codeforces.com/contest/2117/submission/323773579

源代码

// Problem: G. Omg Graph
// Contest: Codeforces - Codeforces Round 1029 (Div. 3)Codeforces 第 1029 轮（第 3 组）
// URL: https://codeforces.com/contest/2117/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 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>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

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

*/
vector<arr2> g[MAXN];		// 最小生成树
bitset<MAXN> vis;
inline void init(){
	FOR(i,0,N+5){g[i].clear();vis[i]=false;}
}
struct DSU {  // 并查集
  vector<int> fa, siz;
  int ln;
  DSU(int n) {
    ln = n;
    fa.resize(ln + 5, 0), siz.resize(ln + 5, 0);
    FOR(i, 1, n) {
      fa[i] = i;
      siz[i] = 1;
    }
  }
  int find(int x) {
    while (fa[x] != x) {
      x = fa[x];
      fa[x] = fa[fa[x]];
    }
    return x;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return false;
    }
    siz[x] += siz[y];
    fa[y] = x;
    return true;
  }
  int size(int x) { return siz[find(x)]; }
  int countFa() {
    int res = 0;
    FOR(i, 1, ln) {
      if (fa[i] == i) ++res;
    }
    return res;
  }
};
ll mxW[MAXN][2],mnW[MAXN][2];
void dfs(ll node,ll wei,ll ci){
	vis[node]=true;
	mxW[node][ci]=wei;
	FOR(i,0,SZ(g[node])-1){
		ll lnode=g[node][i][0],w=g[node][i][1];
		if(vis[lnode]) continue;
		dfs(lnode,max(wei,w),ci);
	}
}
void dfsn(ll node,ll wei,ll ci){
	vis[node]=true;
	mnW[node][ci]=wei;
	FOR(i,0,SZ(g[node])-1){
		ll lnode=g[node][i][0],w=g[node][i][1];
		if(vis[lnode]) continue;
		dfsn(lnode,min(wei,w),ci);
	}
}
arr3 edge[MAXN];
inline void solve(){
	cin>>N>>M;
	init();
	priority_queue<arr3,vector<arr3>,greater<arr3> > pq;
	FOR(i,1,M){
		ll u,v,w;
		cin>>u>>v>>w;
		pq.push({w,u,v});
		edge[i]={u,v,w};
	}
	DSU fa(N);
	// ll mnw=pq.top()[0];
	vector<arr2> wp;		// wait processing
	while(!pq.empty()){		// kruskal
		arr3 t=pq.top();pq.pop();
		ll w=t[0],u=t[1],v=t[2];
		// if(w==mnw) wp.pb({u,v});
		if(!fa.same(u,v)){
			fa.merge(u,v);
			g[u].pb({v,w});
			g[v].pb({u,w});
		}
	}
	dfs(1,0,0);
	FOR(i,0,N+5) vis[i]=false;
	dfs(N,0,1);
	FOR(i,0,N+5) vis[i]=false;
	dfsn(1,INF,0);
	FOR(i,0,N+5) vis[i]=false;
	dfsn(N,INF,1);
	ll ans=INF;
	mnW[1][0]=0,mnW[N][1]=0;
#ifdef LOCAL
    FOR(i,1,N){
    	debug(i);
    	debug(mxW[i][0]);
    	debug(mxW[i][1]);
    }
     FOR(i,1,N){
    	debug(i);
    	debug(mnW[i][0]);
    	debug(mnW[i][1]);
    }
#endif
	FOR(i,1,M){
		ll u=edge[i][0],v=edge[i][1],w=edge[i][2];
		ll lans=INF,lans2=INF;
		lans=min(lans,max({mxW[u][0],mxW[v][1],w}));
		lans=min(lans,max({mxW[v][0],mxW[u][1],w}));
		lans2=min(lans2,min(mnW[u][0],mnW[v][1]));
		lans2=min(lans2,min(mnW[v][0],mnW[u][1]));
		lans2=max(lans2,edge[i][2]);
		ans=min(ans,lans+lans2);
#ifdef LOCAL
	debug(u);
	debug(v);
    debug(ans);
    debug(lans);
    debug(lans2);
    debug(mxW[u][0]);
    cerr<<"\n";
#endif
	}
	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/2117/submission/323773579
*/

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

CF-1029-F. Wildflower

Posted on 2025-06-09 Edited on 2026-02-17

思路讲解

注意到，根据题设条件，树必须为严格的“Y”||”1”。

AC代码

源代码

// Problem: F. Wildflower  F. 野花
// Contest: Codeforces - Codeforces Round 1029 (Div. 3)Codeforces 第 1029 轮（第 3 组）
// URL: https://codeforces.com/contest/2117/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 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,K,lT;
/*

*/
vector<ll> g[MAXN];		// 记得要清空
ll vis[MAXN],dp[MAXN];
inline void init(){
	FOR(i,0,N+5){
		g[i].clear();
	}
	FOR(i,0,N+5){
		vis[i]=false;
	}
}
ll tNode=0,ls=0,rs=0;
ll dfs(ll node){
	ll ret=0;
	vis[node]=true;
	FOR(i,0,SZ(g[node])-1){
		ll lnode=g[node][i];
		if(vis[lnode]) continue;
		ret+=dfs(lnode);
	}
	if(ret==0) ret=1;
	return ret;
}
ll sdfs(ll node){
	ll ret=1,up=0;
	vis[node]=true;
	ll cnt=0;
	FOR(i,0,SZ(g[node])-1){
		ll lnode=g[node][i];
		if(vis[lnode]) continue;
		up=ret;
		ret+=sdfs(lnode);
		++cnt;
	}
	if(cnt==2){
		tNode=node;
		ls=up-1;
		rs=ret-up;
	}
	return ret;
}
ll binpow(ll a,ll k,const ll &p){	// 迭代快速幂
	ll res=1;
	while(k>0){
		if((k&1)==1) res=a*res%p;
		a=a*a%p;
		k>>=1;
	}
	return res;
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N-1){
		ll u,v;
		cin>>u>>v;
		g[u].pb(v);g[v].pb(u);
	}
	ll ret=dfs(1);
	FOR(i,0,N+5){
		vis[i]=false;
	}
	if(ret==1){
		cout<<binpow(2,N,mod)<<"\n";
	}else if(ret==2){
		sdfs(1);
		ll line=N-ls-rs;
		ll mx=max(ls,rs),mn=min(ls,rs);
		ll ans=binpow(2,line,mod)*binpow(2,mx-mn,mod);
		ans+=binpow(2,line,mod)*binpow(2,mx-mn-1,mod);
		// if(mx-mn-1>=0){ans+=binpow(2,line,mod)*binpow(2,mx-mn-1,mod);}
		ans%=mod;
		cout<<ans<<"\n";
#ifdef LOCAL
    debug(line);
    debug(ls);
    debug(rs);
#endif
	}else{
		cout<<0<<"\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/2117/submission/323644092
*/

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

注意，写两种dfs记得要清空vis数组。

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

Posted on 2025-06-07 Edited on 2026-02-17

思路讲解

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

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

💡 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
*/