一本通————1221 分成互质组

1001-高同学

发表文章数:265

热门标签

首页 » LeetCode » 正文

1221:分成互质组

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 4533     通过数: 2089

【题目描述】

给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?

【输入】

第一行是一个正整数n。1 ≤ n ≤ 10。

第二行是n个不大于10000的正整数。

【输出】

一个正整数,即最少需要的组数。

【输入样例】

6
14 20 33 117 143 175

【输出样例】

3

【来源】

No

 

代码如下:

#include <bits/stdc++.h>
#define MAXN 10500
using namespace std;
int a[MAXN];
int cnt[MAXN];
int t;
bool ok(int x)    //这里用了一个数组cnt来记录同一个组内的数可以被哪些数整除 
{
    for(int i=2; i<x; i++)
    {
        if(x%i==0)
        {
            if(cnt[i])    //说明组内已有其它数可以被i整除,即x与组内的数不是互质
            {
                return false;
            }else
            {
                cnt[i]++;
            }
        }
    }
    return true;
}

void dfs(int k,int x)
{
    for(int i=k; i<t; i++)        //多整个数进行查找
    {
        if(ok(a[i]))    //如果与组内的数互质
        {
            a[i]=-1;        //说明这个数已经在别的组里了
            k++;
            dfs(k,a[k]);   //注意不要进行回溯
        }
    //    cout<<"a[i]="<<a[i]<<endl;
    }
    return ;
}

int main()
{
    int i,ans=0;
    cin>>t;
    for(i=0; i<t; i++)
    {
        cin>>a[i];
    }
    for(i=0; i<t; i++)
    {
        if(a[i]!=-1)
        {
            ans++; //每调用一次dfs,就多一个分组

            memset(cnt,0,sizeof(cnt)); //记得要清零
            dfs(i,a[i]);
        }
    }

    cout<<ans<<endl;
    return 0;
}
/*
6
14 20 33 117 143 175
*/

 

标签:

拜师教育学员文章:作者:1001-高同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《一本通————1221 分成互质组》 发布于2020-02-14

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录