欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2020牛客NOIP赛前集训营-普及组(第二场)D-变换

程序员文章站 2022-06-18 13:56:27
...

题目

2020牛客NOIP赛前集训营-普及组(第二场)D-变换

2020牛客NOIP赛前集训营-普及组(第二场)D-变换


对于这些操作…其实就是相对的对第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);
} 
相关标签: 思路