企业官网建设流程全解析

我不是酸菜鱼

时间限制：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_{i=1}^{n} a_ig=∏i=1n​ai​，需要你找到一个最大的自然数k kk满足g % 2 k = 0 g \% 2^k = 0g%2k=0

叁秋：这些数最大的取值范围是什么呢？

溪染：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: Can't 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_{i=1}^{n} c_ik=i=1∑n​ci​
• 目标：求和得到最大的k kk，使得g m o d 2 k = 0 g \bmod 2^k = 0gmod2k=0。

2. 算法实现

1. 逐数统计：对每个a i a_iai​，计算其二进制末尾零的个数。
   • 使用 C++ 内置函数__builtin_ctzll(x)，直接返回unsigned long long变量x的末尾连续 0 的个数（即因子2 22的指数）。
   • 也可用循环while (x % 2 == 0) { cnt++; x /= 2; }实现，但内置函数效率更高。
2. 累加：将每个数的c i c_ici​累加到变量s。
3. 输出：输出累加结果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即可。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll x;ll s=0;cin>>x;while(cin>>x)s+=__builtin_ctzll(x);cout<<s<<endl;return0;}