Codeforces Round #511 (Div. 2)C. Enlarge GCD
程序员文章站
2022-05-09 16:18:04
...
http://codeforces.com/contest/1047/problem/C
直接暴力即可。
首先求出所有数的gcd
然后计数:每个数/gcd 结果的个数
最后直接线性筛 边筛边判断 找到含有共同因子最多的数字 去掉不含有这个公共因子的数字 gcd就会变大
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=1.5e7+5;
int n, g, ans, a[N], cnt[M], vis[M];
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
scanf("%d",&a[i]);
g = __gcd(a[i],g);
}
for(int i = 1;i <= n;i ++){
cnt[a[i] / g] ++;
}
for(int i = 2;i < M;i ++){
int tmp = 0;
if(!vis[i]){
for(int j = i;j < M;j += i){
vis[j] = 1;
tmp += cnt[j];
}
}
ans = max(ans, tmp);
}
printf("%d\n",ans?n-ans:-1);
}
上一篇: js基础闭包练习题
下一篇: ECMA6新增语法(待续...)
推荐阅读
-
Codeforces Round #320 (Div. 2) C. A Problem about Polyline ( 数学 )
-
Codeforces Round #654 (Div. 2)-C. A Cookie for You
-
Educational Codeforces Round 85 (Rated for Div. 2) C. Circle of Monsters(前缀和 预处理 贪心)
-
Codeforces Round #651 (Div. 2) C. Number Game
-
Codeforces Round #668 (Div. 2)-C. Balanced Bitstring
-
Educational Codeforces Round 99 (Rated for Div. 2) C. Ping-pong
-
Codeforces Round #256 (Div. 2) C. Painting Fence(分治贪心)_html/css_WEB-ITnose
-
Codeforces Round #277 (Div. 2)-C. Palindrome Transformation (贪心)_html/css_WEB-ITnose
-
Codeforces Round #277 (Div. 2)-C. Palindrome Transformation (贪心)_html/css_WEB-ITnose
-
C. Mortal Kombat Tower(动态规划)Educational Codeforces Round 95 (Rated for Div. 2)