Codeforces Round #511 (Div. 1)

A. Enlarge GCD
题意:给你N个数让你从中删除最小的数使得所有数的公因子变大,如果不能变大则输出-1
题解:先求出所有数的最大公因子,
这儿我用的是STL里面的函数__gcd(a,b),需要注意的是这个函数前面有两条下划线,然后函数是泛型的。和gcd是一样的。
然后我用线性筛求出所有的质数,根据唯一分解定理将每个数含有的所有质因数全部算出来,然后统计出现次数最多的质因数,然后输出。

#include <bits/stdc++.h>

const int MAXN = 15000000;

using namespace std;

int n,cnt,g,a[MAXN+5],p[MAXN+5],sum[MAXN+5],ans = MAXN;
bool vis[MAXN+5];

inline void pre()
{
    for(int i = 2;i <= MAXN;i++){
        if(!vis[i]){
            p[++cnt] = i;
        }
        for(int j = 1;j <= cnt && i * p[j] <= MAXN;j++){
            vis[i*p[j]] = true;
        }
    }
}

inline int read(){
    int x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <= ch&& ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

int main()
{
    pre();n = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    g = 0;
    for(int i = 1;i <= n;i++) g = __gcd(g,a[i]);
    for(int i = 1;i <= n;i++) a[i] /= g;
    
    for(int i = 1;i <= n;i++){
        for(int j = 1;p[j]*p[j] <= a[i];j++)
            if(!(a[i]%p[j])){
                sum[p[j]]++;
                while(!(a[i]%p[j]))a[i] /= p[j];
            }
        if(a[i] != 1) sum[a[i]]++;
    }
    for(int i=2; i<=MAXN; i++){
        ans = min(ans, n-sum[i]);
    }
    if(ans == n) printf("-1\n");    
    else printf("%d\n",ans);
    
    return 0;
} 

B. Little C Loves 3 II
题意:问你在N*M的棋盘中最多按照规定最多放下多少的棋子。每次放两个棋子而两个棋子的曼哈顿距离为3
题解:我看的一个大佬的博客写的。
Tiw_Air_OAO

//https://blog.csdn.net/Tiw_Air_Op1721/article/details/82811681#_73

#include <bits/stdc++.h>

using namespace std;

long long n,m;

int main(){
    scanf("%lld %lld",&n,&m);
    if(n > m) swap(n,m);
    if(n == 1){
        if(!(m%6)) printf("%lld",m);
        else if((m%6) <= 3) printf("%lld",m-(m%6));
        else printf("%lld",m-6+(m%6));
    }
    else if(n == 2){
        if(m == 2) printf("0");
        else if(m == 3) printf("4");
        else if(m == 7) printf("12");
        else printf("%lld",m*2);
    }
    else 
    {
        if(n & 1 && m & 1) printf("%lld",n*m-1);
        else printf("%lld",n*m);
    }
}
Last modification:October 3rd, 2018 at 08:59 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment