【Openjudge】互質群に分ける
7834:互質グループに分割
合計時間制限:1000 msメモリ制限:65536 kBは、所与のn個の正の整数を記述し、それらをグループ化し、各グループの任意の2個の数が互いに質を交換するようにする.少なくともいくつのグループに分けますか?
入力
最初の行は正の整数nです.1 <= n <= 10. 2行目はn個の10000以下の正の整数である.
しゅつりょく
正の整数、すなわち最小必要なグループ数.サンプル入力
サンプル出力:3出所2008年第13回「華羅庚金杯」少年数学招待試合決勝第5題
【解析】
この問題には2つの方法があります.ここでは、第1の方法に重点を置いて、さまざまな考え方について、コードに移行しました.
方法1:
ステータス:Accepted
方法2:
合計時間制限:1000 msメモリ制限:65536 kBは、所与のn個の正の整数を記述し、それらをグループ化し、各グループの任意の2個の数が互いに質を交換するようにする.少なくともいくつのグループに分けますか?
入力
最初の行は正の整数nです.1 <= n <= 10. 2行目はn個の10000以下の正の整数である.
しゅつりょく
正の整数、すなわち最小必要なグループ数.サンプル入力
6
14 20 33 117 143 175
サンプル出力:3出所2008年第13回「華羅庚金杯」少年数学招待試合決勝第5題
【解析】
この問題には2つの方法があります.ここでは、第1の方法に重点を置いて、さまざまな考え方について、コードに移行しました.
方法1:
ステータス:Accepted
#include
using namespace std;
int n,ans=1e9+1;
bool flag;
int a[10010],b[10010];//a[]
int panduan(int a,int b)//
{
if(b==0)return a;
return panduan(b,a%b);
}
void dfs(int x,int y)// x , y
{
if(x==n+1)// , ,
{
ans=min(ans,y);
return;
}
for(int i=1;i<=y;i++)//
{
flag=true;
for(int j=1;j// ‘=’, ‘=’, , x=1 , 。
{
if(b[j]==i)
{
if(panduan(a[x],a[j])!=1)//
{
flag=false;// , ,
break;//
}
}
}
if(flag)// , ,
{
b[x]=i;//
dfs(x+1,y);// ,
b[x]=0;//
}
}
b[x]=y+1;// 1
dfs(x+1,y+1);//
b[x]=0; //
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
dfs(1,1);// ( , )
cout<return 0;
}
方法2:
#include
#include
int n,a[20],b[20],c=1;
int fun(int x,int y) //
{
if(!y) return x; //y==0
return fun(y,x%y);
}
int main()
{
memset(b,1,sizeof(b)); // "b[j]*=a[i];"
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
b[1]=a[1];
for(int i=2;i<=n;i++)
{
int j;
for(j=1;j<=c;j++)
if(fun(a[i],b[j])==1) // 1,
{
b[j]*=a[i];
break;
}
if(j-1==c) // "break"
b[++c]=a[i];
}
printf("%d",c);
}