UVALive 5791 Candy's Candy 解题报告
比赛总结
题目
题意：
有f种口味的糖果，现在要把每颗糖果分到一些packs里面去。packs分两种：
flavored pack：只有一种口味。
variety pack：每种口味都有。
求满足下列要求的分法有多少种：
1、每个pack至少有两颗糖果。
2、所有pack的糖果数相同。
3、variety pack 里每种口味的糖果数量相同。
4、至少一个variety pack。
5、每种口味至少一个flavored pack。
题解：
设一个pack 的糖果数为lim。
由3知lim是f的倍数。并且去掉variety packs后，剩下的每种糖果间的差值还跟原来一样，要将它们分完必须都是lim的倍数，也就是差值也是lim的倍数，那么最大公倍数也是lim 的倍数。
现在枚举所有可能的lim，由于两种pack糖果数量一样，那么对于同一种糖果，两种pack消耗的数量分别是lim和lim/f。那么我们可以先将其全部分成variety pack，然后再任选出kn个拆分成k个flavored pack。
//Time:136ms//Length：1127B#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <iostream>using namespace std;#define MAXN 100005#define INF 1000000007int num[MAXN],arr[MAXN],n,mlen,r;int gcd(int a,int b){ while(a%b!=0) a%=b,swap(a,b); return b;}int cal(int lim){ if(mlen%lim!=0) return 0; int tmp=r-lim-lim/n; if(tmp%(lim/n)!=0) return 0; tmp/=(lim/n); return tmp/n+1;}int main(){ freopen("/home/moor/Code/input","r",stdin); while(scanf("%d",&n)&&n) { long long sum=0,ans=0; r=INF; for(int i=0;i<n;++i) scanf("%d",&num[i]),r=min(r,num[i]),sum+=num[i]; mlen=0; for(int i=0;i<n;++i) if(r!=num[i]) { mlen=num[i]-r; for(int j=i+1;j<n;++j) if(r!=num[j]) mlen=gcd(mlen,num[j]-r); break; } for(long long i=n;i*i<=sum;i+=n) if(n%i==0) { ans+=cal(i); if(i*i!=n) ans+=cal(n/i); } cout<<ans<<'\n'; } return 0;}