寒蝉凄切，对长亭晚，骤雨初歇。都门帐饮无绪，留恋处，兰舟催发。执手相看泪眼，竟无语凝噎。念去去，千里烟波，暮霭沉沉楚天阔。
多情自古伤离别，更那堪，冷落清秋节！今宵酒醒何处？杨柳岸，晓风残月。此去经年，应是良辰好景虚设。便纵有千种风情，更与何人说！
——宋·柳永《雨霖铃》
字虽好，只是柳永伤感。执手相看泪眼，竟无语凝噎。太不合此情此景。
——爱新觉罗氏胤禛

西施与范蠡泛舟而去……不对，场景不对，咳咳。在甄嬛前往蓬莱洲之前，她与皇上在碧桐书院告别。为了这可能会长达数月的离别，两个人都似乎有很多话要对对方说，却都无语凝噎。这时，皇上突然发话：“嬛嬛啊，既然你我都说不出话来，那这时间也不好打发，我们来数三角形吧。”为了满足皇上突发而来的童趣，甄嬛欣然陪同了。可这……纸上是一张n*m的格子方阵，即有(n+1)*(m+1)个格点。每个格子都是边长为1的正方形。而他们要数的，则是任取3个格点作为三角形的顶点所形成的直角三角形且该三角形面积为s/2的个数。甄嬛数的头都晕了，她现在只想知道满足条件的三角形个数 mod (10^9+7)

输入格式：

第一行3个正整数n，m，s, 意义如题

输出格式：

仅一个整数，为甄嬛与满足条件的三角形个数 mod (10^9+7)

样例输入：

1 1 1

样例输出：

4

数据范围：

对于10%的数据：n<=10
对于另外40%的数据：s为质数
对于100%的数据：1<=n,m,s<=10^8

时间限制：

1S

空间限制：

128M

三角形abc边上总有两个相似三角形.我们设相似比为k,且k>=1.

在上图中,我们要知道a,b,k分别是多少,可以通过枚举的方法实现.

由于:AB*BC/2=S/2,则根号(a*a+b*b)*根号(ka*ka+kb*kb)=S,化简得k(a*a+b*b)=S.

由于S在1e8范围内,我们可以枚举a,b,用根号S*根号S的时间(其实远远不到).

由于我们要保证k>=1,所以a*a+b*b<=S.

而比例系数并不一定是整数,整数的应该是a,b,ka,kb,所以不能掉下这个坑啊.

在上图中,整个三角形的横向长度为la=a+kb,纵向长度为lb=max(b,ka);

所以这一种情况中,合法三角形数量为max(0,n-la+1)*max(0,m-lb+1).

由于可以旋转,即横向长度和纵向长度是相对的,所以可以将la和lb互换.

这种情况中,合法三角形数量为max(0,n-la+1)*max(0,m-lb+1).

又由于可翻转性和对称性,同一个形状的三角形(不考虑横纵向)在同一个矩形内可以算4次,即

合法三角形数量为max(0,n-la+1)*max(0,m-lb+1)*4+max(0,n-la+1)*max(0,m-lb+1)*4.

但是需要注意的是,当a*a+b*b=s的时候,说明k=1,即两个相似三角形全等.

此时,我们枚举的这个直角三角形对于横纵向其实是同样的情况(即不存在横纵向之分,或者说,在横向统计和纵向统计中都会统计到这一种三角形),所以这种情况

合法三角形数量为(max(0,n-la+1)*max(0,m-lb+1)*4+max(0,n-la+1)*max(0,m-lb+1)*4)/2.

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int TT=1000000007; 9 int n,m,s,cnt,fac[20005];10 LL ans,c1,c2,la,lb;11 int main(){12     cin>>n>>m>>s; cnt=0; ans=0;13     for (int i=1; i<=sqrt(s); i++) if (s%i==0) fac[++cnt]=i;14     for (int i=1; i<=cnt; i++){15         c1=n-fac[i]+1,c2=m-(s/fac[i])+1;16         if (c1>0&&c2>0) ans=(ans+(LL)c1*c2)%TT;17         if (fac[i]*fac[i]==s) continue;18         c1=m-fac[i]+1,c2=n-(s/fac[i])+1;19         if (c1>0&&c2>0) ans=(ans+(LL)c1*c2)%TT;20     }21     ans*=4; ans%=TT;22     for (LL a=1; a*a<=s; a++)23         for (LL b=1; a*a+b*b<=s; b++){24             LL t=a*a+b*b;25             if ((s*a)%t==0&&(s*b)%t==0){26                 la=a+(s*b)/t,lb=max((s*a)/t,b);27                 c1=max(0LL,n-la+1),c2=max(0LL,m-lb+1);28                 if (t==s) ans+=c1*c2*2; else ans+=c1*c2*4;29                 c1=max(0LL,m-la+1),c2=max(0LL,n-lb+1);30                 if (t==s) ans+=c1*c2*2; else ans+=c1*c2*4;31                 ans%=TT;32             }33         }34     printf("%lld",(ans+TT)%TT);35     return 0;36 }

View Code