#C231111A. 种树(plant)

标签（Label）

数学（因数个数定理）
贪心

网址（Website）

$\qquad$洛谷：种树

$\qquad$SPOJ：种树 - 题目

$\qquad$题解：种树 - 题解

题解（Solution）

$\qquad$有一个性质：一个数的因数个数为其质因数分解后每个质数的指数大小+1的乘积。

$\qquad$从这个角度去想就发现会了：每次施肥先把当前的 $w$ 有的质因数 $k$ 扔给当前的 $p_i$ 没有的质因数，这样贡献能直接 $+2$ ，同时让小的数变大总是优于让大的数变的更大的，这个可以用和定差小积大来理解（其实就是一个二次函数的原理）。

$\qquad$然后搞个优先队列（堆）稍稍维护一下就好啦~

$\qquad$时间复杂度：$O(n\sqrt{n}\times logn)$

代码（Code）

#include<bits/stdc++.h>
#include<bitset>
#include<map>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int mod = 998244353;
const int N = 10123;
bool ST;
priority_queue<P,vector<P>,greater<P>> q; 
bitset<N> vst;
int h[N];
int n,w,ans=1;
int ton[N],use[N];
bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n"; 
	string str("plant");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>n>>w;For(i,1,n) h[i]=input();
	//w的质因数 
	{
		int x=w,t=sqrt(x);
		for(int j=2;j<=t && x!=1;){
			if(x%j==0) x/=j,vst[j]=true,ton[j]++;
			else j++;
		}if(x!=1) ton[x]++,vst[x]=true;
	}
	
	For(i,1,n){
		map<int,int> mp;
		int x=h[i],t=sqrt(x);
		for(int j=2;j<=t && x!=1;){
			if(x%j==0) x/=j,mp[j]++;
			else j++;
		}if(x!=1) mp[x]++;
		for(int j=vst._Find_first();j<=w;j=vst._Find_next(j)){
			if(!mp.count(j) && ++use[j]<=ton[j]) q.push({0,j});
		}
		for(auto p:mp){
			int x=p.first,k=p.second;
			if(w%x) ans=ans*(k+1)%mod;
			else q.push({k,x});
		}
	}

	while(q.size()){
		int x=q.top().second,k=q.top().first;q.pop();
		if(w!=1 && w%x==0){
			q.push({k+1,x});
			w/=x;
		}else{
			if(k==0) continue;
			ans=ans*(k+1)%mod;
		}
	}
	cout<<ans<<'\n';
	return 0;
}