我不是酸菜鱼时间限制1秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述溪染叁秋问你一个问题。叁秋你说。溪染给你n nn个数分别为a 1 , a 2 , a 3 , … , a n a_1,a_2,a_3,…,a_na1​,a2​,a3​,…,an​定义一个数g ∏ i 1 n a i g\prod_{i1}^{n} a_ig∏i1n​ai​需要你找到一个最大的自然数k kk满足g % 2 k 0 g \% 2^k 0g%2k0叁秋这些数最大的取值范围是什么呢溪染n ≤ 5 × 10 6 , 1 ≤ a i ≤ 2 15 n \le 5 \times 10^6,1 \le a_i \le 2^{15}n≤5×106,1≤ai​≤215叁秋不会。溪染氧化钙你真的是条酸菜鱼叁秋什么意思溪染C a O CaOCaO你又酸又菜又多余于是溪染又找到了你为了证明自己不是酸菜鱼你需要解出这个问题。输入描述第一行输入一个正整数n ( 1 ≤ n ≤ 5 × 10 6 ) n(1 \le n \le 5 \times 10^6)n(1≤n≤5×106)。第二行输入n nn个正整数a i ( 1 ≤ a i ≤ 2 15 ) a_i(1 \le a_i \le 2^{15})ai​(1≤ai​≤215)表示这n nn个正整数的值。输出描述仅一行表示问题的答案k kk即最大的自然数k kk满足KaTeX parse error: Cant use function \) in math mode at position 8: g \\(\%\̲)̲ 2^k 0。示例1输入5 32714 7146 4351 24978 31703输出3备注% \%%表示取余数运算。解题思路本题是质因数分解中因子 2 计数的简单统计问题。要求计算所有数的乘积g gg中因子2 22的幂次k kk即g gg能被2 k 2^k2k整除的最大k kk。由于乘法中因子 2 的指数可叠加只需分别统计每个a i a_iai​中 2 的幂次并求和即可。1. 问题等价转化因子 2 的提取对于任意正整数a i a_iai​记c i c_ici​为a i a_iai​的二进制表示末尾连续0 00的个数即满足a i 2 c i × odd a_i 2^{c_i} \times \text{odd}ai​2ci​×odd。则乘积g ∏ a i g \prod a_ig∏ai​中因子2 22的总幂次为k ∑ i 1 n c i k \sum_{i1}^{n} c_iki1∑n​ci​目标求和得到最大的k kk使得g m o d 2 k 0 g \bmod 2^k 0gmod2k0。2. 算法实现逐数统计对每个a i a_iai​计算其二进制末尾零的个数。使用 C 内置函数__builtin_ctzll(x)直接返回unsigned long long变量x的末尾连续 0 的个数即因子2 22的指数。也可用循环while (x % 2 0) { cnt; x / 2; }实现但内置函数效率更高。累加将每个数的c i c_ici​累加到变量s。输出输出累加结果s。3. 复杂度分析时间复杂度O ( n ) O(n)O(n)每个数只需一次位运算n ≤ 5 × 10 6 n \le 5 \times 10^6n≤5×106在关闭流同步后使用cin也可在 1 秒内完成若担心常数可改用快速读入。空间复杂度O ( 1 ) O(1)O(1)仅需存储当前数字和累加和。总结利用二进制末尾零个数与因子 2 指数的一一对应关系通过内置函数高效求和无需实际计算大数乘积在线性时间内完成。代码简要说明先用cin x读取n nn之后循环读取每个a i a_iai​由于只有一个测试用例直接while (cin x)读到 EOF实际读入n nn个数。对每个x xx调用__builtin_ctzll(x)将返回值累加到s。输出s即可。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll x;ll s0;cinx;while(cinx)s__builtin_ctzll(x);coutsendl;return0;}