ACM 10637 Q10637: Coprimes
作法: 建表+DFS
程式碼1的速度<程式碼2的速度
但速度仍然不夠快
/*************************************************************/
#include<stdio.h>
#include<stdlib.h>
int gcd(int a,int b)
{
int temp;
while(a%b)
{
temp=a;
a=b;
b=temp%b;
}
return b;
}
int line[101]={0},GCD[101][101]={0};
int n,m;
void DFS (int now,int sum,int a)
{
int b;
if(now==m&&sum==n)
{
for(b=0;b<m-1;b++) printf("%d ",line[b]);
printf("%d",line[b]);
printf("\n");
return;
}
if(sum>=n) return;
for(a=a;a<=n-sum;a++)
{
for(b=0;b<now;b++)
if(GCD[line[b]][a]!=1) break;
if(b==now&&n-sum>=a)
{
line[now]=a;
DFS (now+1,sum+a ,a);
}
}
}
main()
{
int a,b;
for(a=1;a<=100;a++)
for(b=1;b<=100;b++)
GCD[a][b]=gcd(a,b);
int t,time=1;
while(scanf("%d",&t)==1)
while(t--)
{
scanf("%d %d",&n,&m);
printf("Case %d:\n",time++);
DFS (0,0,1);
}
return 0;
}
/***************************************/
#include<stdio.h>
#include<stdlib.h>
int ppt[101][10]={0},top[101]={0};
int prime()
{
int a,b;
ppt[1][0]=1;
for(a=2;a<101;a++)
if(top[a]==0)
for(b=1;a*b<=101;b++)
ppt[a*b][top[a*b]++]=a;
}
int line[101]={0},appear[101]={0};
int n,m;
void DFS (int now,int sum,int a,int flag)
{
int b;
if(now==m&&sum==n)
{
for(b=0;b<m-1;b++) printf("%d ",line[b]);
printf("%d",line[b]);
printf("\n");
return;
}
if(sum>=n) return;
for(a=a;a<=n-sum;a++)
{
if(flag==1&&a%2==0) continue;
int find=0;
for(b=0;b<top[a];b++)
if(appear[ppt[a][b]]==1) {find=1;break;}
if(find==0)
{
line[now]=a;
appear[ppt[a][0]]=1;appear[ppt[a][1]]=1;appear[ppt[a][2]]=1;appear[ppt[a][3]]=1;
DFS (now+1,sum+a ,a+(a!=1),(a%2==0));
appear[ppt[a][0]]=0;appear[ppt[a][1]]=0;appear[ppt[a][2]]=0;appear[ppt[a][3]]=0;
}
}
}
main()
{
int a,b;
int t;
prime();
while(scanf("%d",&t)==1)
{
int time=1;
while(t--)
{
scanf("%d %d",&n,&m);
printf("Case %d:\n",time++);
DFS (0,0,1,0);
}
}
return 0;
}