今天比赛做的一个题目，不过今天终于感受到了复旦题目有多坑了。
题目的意思是给你一段长为n个单位长度的直线，你可以选择任意连续单位长度的线段组成三角形，可以组成任意你可以组成任意多个三角形，且要求其中所有的三角形相似。现在要你求出，总共有多少种三角形的情况。 详情见题目。
题目的意思明白了以后就可以开始思考具体怎么解题了。
比赛开始的时候我也很费解，到底怎么求出所有的排列组合的情况。
一开始我是这样考虑的，要使得最终的每一个三角形都相似，那么其中所有的三角形必须有一个不小于3的公约数，但是对于三角形的边长怎么不重复地搞出来还是没有办法。
其实是这样来搞的。我们用一个函数f(i)来表示周长为i的独特的三角形的数目有多少。我这里所谓的“独特”，其实是其不会与任何一个周长小于i的三角形相似。但是后来仔细一想就知道是gcd(a,b,c)=1，也就是说三角形的三边互质。同时f[i]表示的只是a不大于b，b不大于c的种类数量。
对于某一个i，其独特的种类数可以用类似容斥原理的方法求得。
什么意思呢？
另某一个中间变量tot=[sigama]f(x)，（x为A的所有的约数），那么f(A)=count（x）-tot。这里count(x)表示周长为x的三角形的总数。
这样就可以得到所有的独特数了。
题目剩下的就比较简单了，枚举独特的三角形的时候对于后面的每一个独立的独特单元，它都有两种组合情况，要么与前面的组合，要么不组合，这样就可以快速幂解决了。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #define maxn 5000500 5 #define M 1000000007 6 #define ll long long 7 using namespace std; 8 9 ll f[maxn]; 10 11 ll count(ll x) 12 { 13 ll tot=0; 14 for (int i=1; i<=x/3; i++) 15 { 16 int tep=x-i; 17 if (tep/2>=max(i,(tep-i)/2+1)) 18 { 19 tot=(tot+tep/2-max(i,(tep-i)/2+1)+1); 20 if (tot>=M) tot-=M; 21 } 26 } 27 return tot; 28 } 29 30 ll get(ll x) 31 { 32 if (f[x]!=0) return f[x]; 33 ll tot=0; 34 for (int i=3; i<=x/2; i++) 35 if (x%i==0) 36 { 37 tot=(tot+get(i)); 38 if (tot>=M) tot-=M; 39 } 42 f[x]=count(x)-tot; 43 if (f[x]<0) f[x]+=M; 44 return f[x]; 45 } 46 47 ll power(ll x,ll y) 48 { 49 ll tot=1; 50 while (y) 51 { 52 if (y&1) tot=(tot*x)%M; 53 x=(x*x)%M; 54 y>>=1; 55 } 56 return tot; 57 } 58 59 int main() 60 { 61 ll n,ans,tep,cas=0; 62 while (scanf("%I64d",&n)!=EOF) 63 { 64 ans=0; 65 for (int i=1; i*i<=n; i++) 66 { 67 if (n%i==0) 68 { 69 tep=get(i); 70 tep=(tep*power(2,n/i-1))%M; 71 ans+=tep; 72 if (ans>=M) ans-=M; 73 74 if (i*i!=n) 75 { 76 tep=get(n/i); 77 tep=(tep*power(2,i-1))%M; 78 ans+=tep; 79 if (ans>=M) ans-=M; 80 } 81 } 82 } 83 84 printf("Case %I64d: %I64d ",++cas,ans); 85 } 86 return 0; 87 }