2009-02-11 21:15:51來源不明
ACM 369 Q369: Combinations
首先先用陣列[階層]把數存好,陣列所存的東西是math[n]~math[m] 值互相對應m格就是m,再來就是把能除的,將那一個除掉,一定能除,但是會可能分散再別的數裡面,所以會用到公因數。
ex.18 6
我會取math[13]=13,math[14]=14....到math[18]=18
然後除1.2.3.4.5.6 這些數字再以上的陣列去搜尋,並把他們除掉
遇到2 math[14]=7;
3 math[15]=5;
4 math[16]=4;
5 math[15]=1;
6 math[16]=2;math[18]=6;
總結 math[13]=13,math[14]=7,math[15]=1,math[16]=2,math[17]=17,math[18]=6
之後再將剩下的通通乘出來,之所以這樣做,是怕途中暴掉,用double又不準確
/*************************************************************/
- #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;
- }
- main()
- {
- int a,b,c,m,n;
- int math[101];
- while(scanf("%d %d",&n,&m)==2&&n!=0)
- {
- printf("%d things taken %d at a time is ",n,m);
- unsigned long long int s=1;
- for(a=1;a<=n;a++)
- math[a]=a;
- if(m>n/2) m=n-m;
- for(a=2;a<=m;a++)
- {
- c=a;
- for(b=n-m+1;b<=n;b++)
- {
- if(math[b]%c==0)
- {
- math[b]=math[b]/c;
- c=1;
- }
- if(gcd(math[b],c)!=1)
- {
- int gg=gcd(math[b],c);
- math[b]=math[b]/gg;
- c=c/gg;
- }
- if(c==1)
- break;
- }
- }
- for(b=n-m+1;b<=n;b++)
- {
- s=s*math[b];
- }
- printf("%llu exactly.\n",s);
- }
- return 0;
- }
/*************************大數版本*****************************/
- #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;
- }
- main()
- {
- int a,b,c,m,n;
- int math[101];
- while(scanf("%d %d",&n,&m)==2&&n!=0)
- {
- printf("%d things taken %d at a time is ",n,m);
- for(a=1;a<=n;a++)
- math[a]=a;
- if(m>n/2) m=n-m;
- for(a=2;a<=m;a++)
- {
- c=a;
- for(b=n-m+1;b<=n;b++)
- {
- if(math[b]%c==0)
- {
- math[b]=math[b]/c;
- c=1;
- }
- if(gcd(math[b],c)!=1)
- {
- int gg=gcd(math[b],c);
- math[b]=math[b]/gg;
- c=c/gg;
- }
- if(c==1)
- break;
- }
- }
- int ans[50]={0};
- ans[0]=1;
- for(b=n-m+1;b<=n;b++)
- {
- for(c=0;c<49;c++)
- ans[c]=ans[c]*math[b];
- for(c=0;c<49;c++)
- {
- if(ans[c]>=10)
- {
- ans[c+1]=ans[c+1]+ans[c]/10;
- ans[c]=ans[c]%10;
- }
- }
- }
- for(a=49;a>=0;a--)
- if(ans[a]!=0)
- {
- for(b=a;b>=0;b--)
- printf("%d",ans[b]);
- break;
- }
- printf(" exactly.\n");
- }
- return 0;
- }