域名解析后怎么做网站,园区做网站,网站 备案号,二维码生成器app洛谷 NOIP 2023 模拟赛 P9836 种树 文章目录 洛谷 NOIP 2023 模拟赛 P9836 种树题目大意思路code 题目大意
路边有 n n n 棵树#xff0c;每棵树的 高度 均为正整数#xff0c;记作 p 1 , p 2 … p n p_1, p_2 \dots p_n p1,p2…pn。
定义一棵树的 宽度 为它高度的…洛谷 NOIP 2023 模拟赛 P9836 种树 文章目录 洛谷 NOIP 2023 模拟赛 P9836 种树题目大意思路code 题目大意
路边有 n n n 棵树每棵树的 高度 均为正整数记作 p 1 , p 2 … p n p_1, p_2 \dots p_n p1,p2…pn。
定义一棵树的 宽度 为它高度的正因数个数这些树能覆盖的距离为它们宽度的乘积你想请你的朋友们来乘凉但你发现这些树能覆盖的距离不够多。
于是你买了总量为 w w w 单位的神奇化肥。你可以施若干次肥每次你可以使用 k k k 单位化肥要求 k k k 必须为当前化肥量的正因数让任意一棵树的高度乘上 k k k同时你剩余的化肥量也会除以 k k k。每次施肥的树可任意选择且每次施肥选择的树不需相同。
你需要最大化这些树所能覆盖的距离并输出这个最大距离。答案对 998244353 998244353 998244353 取模。 n , p , w ≤ 1 0 4 n , p , w \le 10^4 n,p,w≤104
思路
我们把 a i a_i ai 进行质因数分解 a i p 1 b 1 ∗ p 2 b 2 ⋯ a_i p_1^{b_1} * p_2^{b_2}\cdots aip1b1∗p2b2⋯
那么这棵树的宽度就是 ( b 1 1 ) ∗ ( b 2 1 ) ⋯ (b_1 1) * (b_21) \cdots (b11)∗(b21)⋯
那么答案就是把所有的 a a a 进行质因数分解然后把每个质数的总数加一然后乘起来。
对于 w w w 我们也把它质因数分解 w p 1 b 1 ∗ p 2 b 2 ⋯ w p_1^{b_1} * p_2^{b_2}\cdots wp1b1∗p2b2⋯然后把每个 p p p 都分到包含这个质数最小的数上这个可以用一个对来维护。
code
#include bits/stdc.h
#define LL long long
#define fu(x , y , z) for(int x y ; x z ; x )
using namespace std;
const int N 1e4 5;
const LL mod 998244353;
int n , w , vis[N 5] , b[N 5] , b1 , ans1[N][2005];
long long p[N];
struct node {int id , v;bool operator (const node t) const {return v t.v;}
} ;
priority_queuenode , vectornode , greaternode q;
int main () {// freopen (plant.in , r , stdin);int a;scanf (%d%d , n , w);fu (i , 1 , n) scanf (%lld , p[i]);int w1 sqrt (w);int a1;node now;LL ans 1;fu (i , 2 , N) {if (!vis[i]) b[b1] i;fu (j , 1 , b1) {if (i * b[j] N) break;vis[i * b[j]] 1;if (i % b[j] 0) break;}}// fu (i , 1 , 10) cout b[i] ;// return 0;fu (i , 1 , b1) {a 0;while (w % b[i] 0) {w / b[i];a ;}fu (j , 1 , n) {a1 0;while (p[j] % b[i] 0) {a1 ;p[j] / b[i];}q.push((node){j , a1 1});}while (a --) {now q.top();q.pop();now.v ;q.push(now);}while (!q.empty()) {now q.top();q.pop();ans ans * 1ll * now.v % mod;}}printf (%lld , ans);return 0;
}
