HDU 4466 Triangle(12年成都)
转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题目：给出长度为n的铁丝，将铁丝分为若干 部分，每个部分折成三角形，要求所有三角形相似。
三角形三边相等视为相等，三角形顺序不同视为不同
http://acm.hdu.edu.cn/showproblem.php?pid=4466
首先我们考虑周长为m的三角形有多少个
我们假设 a<=b<=c
这里分为两种情况 b=c
那么对于c的上界，c最大取floor((x-1)/2)，因为a最少为1
对于c的下界，c最小取ceil(x/3)
则所有情况为floor((x-1)/2)-ceil(x/3)+1
第二种情况，b!=c
我们考虑(a,b,c)，由于a+b>c ，b<=c-1所以(a,b,c-1)必定也为三角形
另外需要除掉a+b==c+1的情况 ，其中a+b+c=x，可以发现x必定为奇数，数目为floor((x-(x-1)/2)/2)
则得到代码中的递推式
我们还需要把三角形全部化为连长互质的。这里通过线性筛选就可以完成
解释一下这样做的目的。
接下来我们把n分为若干 个部分，每一个部分等长，而且都能组成若干个连长互质的三角形。由于题目要求互质。
我们把其中几个组成在一起，就是和本质三角形相似的大三角形。
假设有i个本质三角形，题目要求顺序不同视为不同，插板即可解决，i-1个空，每个空都可以选择隔开或者不隔开
2^(i-1)种情况，在一起的就组成大三角形
#include<iostream>#include<cstdio>#include<map>#include<cstring>#include<cmath>#include<vector>#include<algorithm>#include<set>#include<string>#include<queue>#define inf 100000005#define M 20005#define N 5000005#define maxn 300005#define eps 1e-10#define zero(a) fabs(a)<eps#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))#define pb(a) push_back(a)#define mp(a,b) make_pair(a,b)#define mem(a,b) memset(a,b,sizeof(a))#define LL long long#define MOD 1000000007#define lson step<<1#define rson step<<1|1#define sqr(a) ((a)*(a))#define Key_value ch[ch[root][1]][0]//#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;int dp[N],fac[N];void Init(){ dp[3]=1; for(int i=4;i<N;i++) { dp[i]=dp[i-1]-ceil(i/3.0)+floor((i-1)/2.0)+1; if(!(i&1)) dp[i]-=floor((i-(i-1)/2.0)/2.0); if(dp[i]>=MOD) dp[i]-=MOD; if(dp[i]<0) dp[i]+=MOD; } fac[1]=1;fac[2]=2; for(int i=3;i<N;i++) { fac[i]=fac[i-1]*2; if(fac[i]>=MOD) fac[i]-=MOD; for(int j=2;i*j<N;j++) { dp[j*i]-=dp[i]; if(dp[j*i]<0) dp[j*i]+=MOD; } }}int main(){ Init(); int cas=0,n; while(cin>>n) { LL ans=0; for(int i=1;i*i<=n;i++) { if(n%i) continue; ans=(ans+(LL)dp[i]*fac[n/i])%MOD; if(i*i!=n) ans=(ans+(LL)dp[n/i]*fac[i])%MOD; } cout<<"Case "<<++cas<<": "<<ans<<endl; } return 0;}