2879. 求三元组个数

这题恐怕只有EOJ可以暴力撸吧……

数字的范围在1000以内

来自渣渣的一点微小的提示
为防重复先排序
为防超时GCD（最小公倍数）存下来，只算依次

include

using namespace std;
int n,ans=0;
int a[600];
int dp[600][600];
int GCD(int aa,int bb)
{
if(aa<bb) swap(aa,bb);
if(bb==0) return aa;
else return GCD(bb,aa%bb);
}

int gcd(int aa,int bb)
{
int& ans=dp[aa][bb];
if(ans!=-1) return ans;
else return ans=GCD(a[aa],a[bb]);
}
int main()
{
cin>>n;
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;i++)
scanf(“%d”,&a[i]);
sort(a,a+n);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
for(int k=j+1;k<=n;k++)
{
if((gcd(i,j)==1 && gcd(i,k)==1 && gcd(j,k)==1) || (gcd(i,j)!=1 && gcd(i,k)!=1 && gcd(j,k)!=1)) ans++;
}
cout<<ans<<endl;
return 0;
}

感觉和dp没什么关系啊。。。哪有什么状态转移，说到底还是数学题。。。

没有任何优化的居然过了，，Goat太强大了

只能说，eoj太快了，，

暴力模拟是最强的！~~EOJ是最快的！~~(我好像打了一条假的删除线QwQ)

果然是先排序再去辗转相除不会超时

include

using namespace std;

int gcd(int a, int b)//辗转相除法求最大公约数
{
//a<b
if(a==1)
return 1;
int c=a;
a=b%a;
b=c;
if(a==0)
return b;
else
return gcd(a,b);
}

bool zhi(int a, int b)
{
if(gcd(a,b)!=1)//判断最大公约数是否为1
return false;
return true;
}

bool judge(int a, int b, int c)
{
int ab=0, bc=0, ac=0;
if(zhi(a,b))//判断是否互质
ab=1;
if(zhi(a,c))
ac=1;
if(zhi(b,c))
bc=1;
if(ab==0&&ac==0&&bc==0||ab==1&&bc==1&&ac==1)//两两互质或两两不互质
return true;
return false;
}

int main()
{
int n, i, j;
int num[500];
cin>>n;
for(i=0;i>num[i];
}
for(i=0;i<n-1;i++)//排序
{
for(j=i+1;jnum[j])
{
int temp=num[i];
num[i]=num[j];
num[j]=temp;
}
}
}

int result=0;
for(i=0;i<n-2;i++)
{
    for(j=i+1;j<n-1;j++)
    {
        for(int k=j+1;k<n;k++)//依次判断，不重复
        {
            if(judge(num[i],num[j],num[k]))//是否满足条件
                result++;
        }
    }
}
cout<<result;

}