2020牛客NOIP赛前集训营-普及组(第二场)D-变换
程序员文章站
2022-06-18 13:56:27
...
题目
解
对于这些操作…其实就是相对的对第i个数乘上或除上某数。
代码
#include<cstdio>
int a[1990001],gcdd,ans,n;
int gcd(int aa,int bb){
if(bb == 0) return aa;
return gcd(bb,aa%bb);
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
gcdd = a[1];
for(int i = 2; i <= n; ++i)
gcdd = gcd(a[i], gcdd);
for(int i = 1; i <= n; ++i){
a[i] = a[i] / gcdd; //先除去这些数相同的部分
while(a[i] % 2 == 0){
++ans;
a[i] /= 2;
}
for(int j = 3; j * j <= a[i]; j += 2){
while(a[i] % j == 0){
++ans;
a[i] /= j;
}
}
if(a[i] > 1) ++ans; //分解质因数..
}
printf("%d",ans);
}