*3 or /2
题目大意:有n个数,每次操作将第i个数*3或/2,得到结果必须为整数,且每次操作必须有一次为/2,求最大操作次数.
一开始看很懵比,感觉肯定是思维题,对着样例猜了个结论竟然就过了大数据。。。
思路:奇数只能 * 3,所以只考虑偶数.对于一个偶数,可以分解成2^n * a,显然a为奇数,那么如果这个偶数乘3为2^n * 3a,3a也显然为奇数,所以证得:任意一个偶数无论乘多少次3它能/2的次数仍然为n不变.
由于次数最大,所以每次只让一个偶数/2。
所以答案就是统计每个偶数为2^n * a中n的和。
C++代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
#define out(a) printf("%d",a)
using namespace std;
int n,cnt;
int a[100050];
int read()
{
int s=0,t=1; char c;
while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
return s*t;
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
a[i]=read();
for (int i=1;i<=n;i++)
if (a[i]%2==0) {
while (true) {
if (a[i]%2==0) cnt++,a[i]/=2;
else break;
}
}
out(cnt);
return 0;
}
