【CSU 1756】Prime

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1756

直接暴力O(n^2logn)过不了两两算gcd

考虑每个数的范围[1,1000]统计一下即可O(1000^2*log(1000))

Notice:1与任何数互质,需要特判(自己与自己互质)

Code1 统计

// <1756.cpp> - Wed Oct 19 08:25:53 2016

// This file is made by YJinpeng，created by XuYike's black technology automatically.

// Copyright (C) 2016 ChangJun High School, Inc.

// I don't know what this program is.

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN=;

inline int gi() {

    register int w=,q=;register char ch=getchar();

    while((ch<''||ch>'')&&ch!='-')ch=getchar();

    if(ch=='-')q=,ch=getchar();

    while(ch>=''&&ch<='')w=w*+ch-'',ch=getchar();

    return q?-w:w;

}

int a[MAXN];

int main()

{

    int T=gi();

    while(T--){

        int n=gi(),ans=;

        memset(a,,sizeof(a));

        for(int i=;i<=n;i++)

            a[gi()]++;

        for(int i=;i<MAXN;i++)

            if(a[i])

                for(int j=i+;j<MAXN;j++)

                    if(__gcd(i,j)==)ans+=a[i]*a[j];

        ans+=a[]>?(a[]-)*a[]/:;//this

        printf("%d\n",ans);

    }

    return ;

}

Code2 vector 本以为记录一下哪些数出现过(结果发现数据水,还跑得慢一点)

// <1756.cpp> - Wed Oct 19 08:25:53 2016

// This file is made by YJinpeng，created by XuYike's black technology automatically.

// Copyright (C) 2016 ChangJun High School, Inc.

// I don't know what this program is.

#include <iostream>

#include <cstdio>

#include <vector>

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN=;

inline int gi() {

    register int w=,q=;register char ch=getchar();

    while((ch<''||ch>'')&&ch!='-')ch=getchar();

    if(ch=='-')q=,ch=getchar();

    while(ch>=''&&ch<='')w=w*+ch-'',ch=getchar();

    return q?-w:w;

}

int a[MAXN];vector<int>b;

inline int gcd(register int a,register int b){

    return b==?a:gcd(b,a%b);

}

int main()

{

    freopen("1756.in","r",stdin);

    freopen("1756.out","w",stdout);

    int T=gi();

    while(T--){

        int n=gi(),ans=,to;

        memset(a,,sizeof(a));

        for(int i=;i<=n;i++)

            a[gi()]++;b.clear();

        for(int i=;i<MAXN;i++)

            if(a[i])b.push_back(i);to=b.size();

        for(int i,o=;i=b[o],o<to;o++)

            if(a[i])

                for(int j,k=o+;j=b[k],k<to;k++)

                    if(gcd(i,j)==)ans+=a[i]*a[j];

        if(b[]==)ans+=a[]>?(a[]-)*a[]/:;//this

        printf("%d\n",ans);

    }

    return ;

}

巴特西

【CSU 1756】Prime

最新文章

热门文章