【noi 2.5_7834】分成互質組（dfs），noi2.5_7834
有2種dfs的方法：
1.存下每個組的各個數和其質因數，每次對於新的一個數，與各組比對是否互質，再添加或不添加如該組。
2.不存質因數了，直接用gcd，更加快。P.S.然而我不知道為什麼RE，若有好心人發現請教教我吧，謝謝~ :-)
下面附上方法1的AC代碼——
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<cmath>
5 #include<iostream>
6 using namespace std;
7
8 int n,ans=12;
9 int a[12];
10 struct node {int t;int p[3000];}
11 b[12];
12
13 int mmin(int x,int y)
14 { return x<y?x:y; }
15 int com(int id,int x)
16 {
17 for (int i=1;i<=b[id].t;i++)
18 if (x%b[id].p[i]==0) return 0;
19 return 1;
20 }
21 void dfs(int id,int h)
22 {
23 int x=a[id];
24 if (id>n) {ans=mmin(ans,h); return;}
25 for (int i=1;i<=h;i++)
26 if (com(i,x))
27 {
28 int y=x,tt=b[i].t;
29 for (int j=2;j<=y;j++)//sqrt(y) wrong
30 if (y%j==0) y/=j, b[i].p[++b[i].t]=j;
31 dfs(id+1,h);
32 b[i].t=tt;
33 }
34 int y=x;
35 b[h+1].t=0;
36 for (int j=2;j<=y;j++)
37 if (y%j==0) y/=j, b[h+1].p[++b[h+1].t]=j;
38 dfs(id+1,h+1);
39 }
40 int main()
41 {
42 scanf("%d",&n);
43 for (int i=1;i<=n;i++)
44 scanf("%d",&a[i]);
45 dfs(1,0);
46 printf("%d",ans);
47 return 0;
48 }
View Code
方法2的90分RE代碼——
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6
7 const int N=15;
8 int n,ans;
9 int a[N],b[N][N],t[N];
10
11 int mmin(int x,int y)
12 { return x<y?x:y; }
13 int gcd(int x,int y)
14 { return (!y)?x:gcd(y,x%y); }
15 bool addit(int x,int i)
16 {
17 for (int j=1;j<=t[i];j++)
18 if (gcd(x,b[i][j])!=1) return false;
19 return true;
20 }
21 void dfs(int x,int h)
22 {
23 if (x>n) {ans=mmin(h,ans);return;}
24 for (int i=1;i<=h;i++)
25 if (addit(a[x],i))
26 {
27 b[i][++t[i]]=a[x];
28 dfs(x+1,h);
29 t[i]--;
30 }
31 b[h+1][++t[h+1]]=a[x];
32 dfs(x+1,h+1);
33 }
34 int main()
35 {
36 scanf("%d",&n);
37 for (int i=1;i<=n;i++)
38 scanf("%d",&a[i]);
39 memset(t,0,sizeof(t));
40 ans=N;
41 dfs(1,0);
42 printf("%d\n",ans);
43 return 0;
44 }
View Code
其實noi上的數據還有個問題——1應該專門放在一組中，而該題數據沒有考慮到這點......
