P9836 种树 题解

蒟蒻在考场上花了 2h45min AC 本题

通过高度求宽度

定义一棵树的宽度为它高度的正因数个数

我们可以预处理 \(10^4\) 之内素数。

	for(ll i=2; i<=10000; i++) {
		if(ok[i]==0) {
			ok[i]=i;
			pr[++nP]=i;
		}
		for(ll j=1; i*pr[j]<=10000&&j<=nP; j++) {
			ok[i*pr[j]]=pr[j];
		}
	}

然后对树的高度分解质因数，即可求出树的宽度。

ll findwidth(ll x,ll in){
	if(x==1) return 1;
	ll cnt=1,j=1,i=1;
	while(x>1){
		ll sum=0;
		while(x%pr[j]!=0){
			j++;
		}
		while(x%pr[j]==0){
			x/=pr[j];
			sum++;
		}
		nums[in][i]=(yin){pr[j],sum};
		cnt*=(sum+1);
		j++;
		i++;
	}
	return cnt;
}

测试点 1~10

\(w=1\)

此时相当于没有化肥可以施，直接用原高度求原宽度并相乘即可。

测试点 11~15

\(n=1\)

此时相当于只有一棵树可以施肥，直接用原高度乘以化肥求宽度即可。

AC解法

我们对于 \(w\) 分解质因数，随后一一枚举，针对每一个质因数遍历 \(n\) 棵树。

以枚举到质因数 \(x\)，第 \(y\) 棵树，且这棵树的高度 \(=x^p \times z (z\in Z , z \bmod x > 0)\) 为例。

若在此施肥，可以使答案乘上 \(\frac{p+2}{p+1}\)，容易发现，p 越小，这次施肥对答案贡献越大。

因此我们遍历得到 p 的最小值及它的位置，更新它的高度和宽度，重复操作，即可以得到最大答案。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=10009;
const ll MOD=998244353;
const ll INF=1e9+9;
ll n,w,p[N],pr[N],ok[N];
ll nP,ans=1;
struct yin{
	ll pr,num;
} nums[N][109];
ll sssm[N];

void input(){
	cin>>n>>w;
	for(ll i=1;i<=n;i++) cin>>p[i];
	for(ll i=2;i<=10000;i++){
		if(ok[i]==0){
			ok[i]=i;
			pr[++nP]=i;
		}
		for(ll j=1;i*pr[j]<=10000&&j<=nP;j++){
			ok[i*pr[j]]=pr[j];
		}
	}
}

ll findwidth(ll x,ll in) {
	if(x==1) return 1;
	ll cnt=1,j=1,i=1;
	while(x>1){
		ll sum=0;
		while(x%pr[j]!=0){
			j++;
		}
		while(x%pr[j]==0){
			x/=pr[j];
			sum++;
		}
		nums[in][i]=(yin){pr[j],sum};
		cnt*=(sum+1);
		j++;
		i++;
	}
	return cnt;
}

void solvew1(){ //即不能增加
	for(ll i=1;i<=n;i++){
		(ans*=findwidth(p[i],1))%=MOD;
	}
	cout<<ans;
}

void solven1(){ //即只能加在一棵树上
	cout<<findwidth(p[1]*w,1);
}

void solve(){
	for(ll i=1;i<=n;i++){
		sssm[i]=findwidth(p[i],i);
	}
	ll j=1;
	while(w>1){
		while(w%pr[j]!=0){
			j++;
		}
		if(w%pr[j]==0){
			w/=pr[j];
		}
		ll mx=INF,nmx=0;
		for(ll i=1;i<=n;i++){
			if(p[i]%pr[j]!=0) {
				mx=min(mx,1ll);
				if(mx==1) nmx=i;
				break;
			}
			else{
				ll k;
				for(k=1;;k++) {
					if(nums[i][k].pr==pr[j]) break;
				}
				mx=min(mx,nums[i][k].num+1);
				if(mx==nums[i][k].num+1) nmx=i;
			}
		}
		sssm[nmx]=sssm[nmx]/mx*(mx+1);
		if(mx==1){
			p[nmx]*=pr[j];
			ll k;
			for(k=1;;k++){
				if(nums[nmx][k].pr==0) break;
			}
			nums[nmx][k]=(yin){pr[j],1};
		}
		else{
			ll k;
			for(k=1;;k++) {
				if(nums[nmx][k].pr==pr[j]) break;
			}
			nums[nmx][k].num++;
		}
	}
	for(ll i=1;i<=n;i++) {
		(ans*=sssm[i]%MOD)%=MOD;
	}
	cout<<ans%MOD;
}

int main(){
	input();
	if(w==1)
		solvew1();
	else if(n==1)
		solven1();
	else
		solve();
	return 0;
}

有问题欢迎提出。