Codeforces Round #511 (Div. 2)

A. Little C Loves 3 I
题意:将一个N分为三个不能被三整除的数
题解:先分出一个1,然后分类判断是否成立来输出1或者2,根据同余定理易证方法是有道理的

#include <bits/stdc++.h>

using namespace std;

int n;

int main()
{
    scanf("%d",&n);
    printf("1 ");
    if((n-2)%3 == 0){
        printf("2 %d",n-3);
    }
    else printf("1 %d",n-2);
} 

B. Cover Points
题意:在第一象限画出一个面积最小的等腰直角三角形,能够将所有的点覆盖在等腰三角形内(上)
题解:
所有的等腰直角三角形的函数表达式均为:
y=-x+d -> y+x=d
于是我们只用找到最大的y+x就是答案啦

#include <bits/stdc++.h>

using namespace std;

int n,ans;

int main()
{
    scanf("%d",&n);
    int u,v;
    for(int i = 1;i <= n;i++){
        scanf("%d %d",&u,&v);
        ans = max(ans,u+v);
    }
    printf("%d\n",ans);
} 

C. 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;
} 
Last modification:October 2nd, 2018 at 10:56 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment