题解：ABC276D - Divide by 2 or 3

题解：ABC276D - Divide by 2 or 3

·题目

链接：Atcoder。

链接：洛谷。

·难度

算法难度：入门。

思维难度：入门。

调码难度：入门。

综合评价：极简。

·算法

数论。

·思路

由大脑可知，最后得到的相等的数一定是所有数的gcd，所以先求出所有数的gcd，之后依次遍历每一个数，求出该数能否除以2、3变成gcd（如果不能直接输出-1退出程序，否则继续做），以及若能变成gcd一共要除多少次（加到ans里）。若没有中途退出，就把ans输出。

·代价

O(n)，A掉。

·细节

实现gcd时可以定义一个g记录，先输入a[1]，把g设成a[1]，之后通过辗转相除法求出所有数的观察到。

对于上文中提到的两个问题，我们可以对a[i]与g作商，并把该数反复除以2、3直到无法整除或已经除到1，如果是无法整除，就说明无法完成任务，否则把除的次数加到ans里。

·代码

#include<bits/stdc++.h>
#define N 1100
using namespace std;
int a[N]={},g=0,ans=0,n=0;
int gcd(int a,int b);
int main(){scanf("%d%d",&n,&a[1]);g=a[1];for(int i=2;i<=n;i++){scanf("%d",&a[i]);g=gcd(g,a[i]);}for(int i=1;i<=n;i++){int tmp=a[i]/g;while(tmp>1&&tmp%2==0){tmp/=2;ans++;}while(tmp>1&&tmp%3==0){tmp/=3;ans++;}if(tmp!=1){printf("-1\n");return 0;}}printf("%d\n",ans);return 0;
}
int gcd(int a,int b){if(a<b){return gcd(b,a);}if(b==0){return a;}return gcd(b,a%b);
}

·注意

gcd千万不要把初始值设置成1，再和每个数运算，否则会直接WA掉。