题目大意:有n个数,每次操作将第i个数*3或/2,得到结果必须为整数,且每次操作必须有一次为/2,求最大操作次数.

一开始看很懵比,感觉肯定是思维题,对着样例猜了个结论竟然就过了大数据。。。

思路:奇数只能 * 3,所以只考虑偶数.对于一个偶数,可以分解成2^n * a,显然a为奇数,那么如果这个偶数乘3为2^n * 3a,3a也显然为奇数,所以证得:任意一个偶数无论乘多少次3它能/2的次数仍然为n不变.

由于次数最大,所以每次只让一个偶数/2。

所以答案就是统计每个偶数为2^n * a中n的和。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define ll long long 7 #define out(a) printf("%d",a) 8 using namespace std; 9 int n,cnt; 10 int a[100050];11 int read()12 {13     int s=0,t=1; char c;14     while (c<'0'||c>'9'){
    if (c=='-') t=-1; c=getchar();}15     while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}16     return s*t;17 }18 int main()19 {20     n=read();21     for (int i=1;i<=n;i++)22       a[i]=read();23     for (int i=1;i<=n;i++)24       if (a[i]%2==0) {25         while (true) {26           if (a[i]%2==0) cnt++,a[i]/=2;27           else break;28         }29     }30     out(cnt);31     return 0;32 }