摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 排容原理 + 生成組合 + GCD

為了方便說明,
先定義LCM(A) 是取A集合的最小公倍數
C(A,B) 是從A個數字中抓B個出來
那麼C是從M個數字抓

答案就是

N/LCM(C(M,0))-N/LCM(C(M,1))+N/LCM(C(M,2))-N/LCM(C(M,3))...

N/LCM(C(M,M))

/**********************************************************/

#include<stdio.h>
#include<stdlib.h>
int n,m,a,b;
int value[51]={0};
int GCD(int a,int b)                 
{                 
  int temp;                 
  while(a%b)                       
   {                       
     temp=a;                       
     a=b;                       
     b=temp%b;                                  
   }     
   return b;                 
}
int way[51]={0};
int sum;
void make (int now,int a,int n,int m,int s,int div)
{
  int b=a,c;
       if(now%2==0) sum-=div/s;
       else sum+=div/s;
  if(now==m+1)  return;
  else
  for(b=a;b<=n;b++)
   {
    way[now]=b;
    make(now+1,b+1,n,m,s/GCD(s,value[way[now]])*value[way[now]],div);
   }
}
main()
{
 while(scanf("%d %d",&n,&m)==2)
    {
     if(n==0&&m==0) break;
     for(a=1;a<=m;a++)
        scanf("%d",&value[a]);
     sum=0;
     make(1,1,m,m,1,n);
     printf("%d\n",sum);
    }
 return 0;  
}