http://codeforces.com/problemset/problem/215/C
题意理解我想了很久,不明白为什么3 4 5的时候只有四个。看了CF原题的hint之后不明白为什么就是那四个。后来终于明白了。那两个等式很重要。原来我敲代码的时候根本不理解这两个等式的意思,就瞎敲,怎么都过不了。
看了别人的代码,又理解了甚久,才算是明白。
首先,这两个等式中的任意一个都可以表示一个长方形(十字可以是宽的)。这一点知道了,代码应该就八九不离十了。
我们去枚举一个长方形(边必须是奇数),如果这个长方形符合条件,我们就去枚举另外一个长方形的长(或宽)即可(因为总面积已经定了)。
CF的题真觉得伤不起,我从昨天晚上做到今天。。。
#include <cstdio> int n,m,s,r; //2 equations represents 2 rectangles!!! //so we enumerate one rectangle's hight and width //how many rectangle with h and m are there in the big given rectangle __int64 f(int h,int w){ return (n - h + 1) * (m - w + 1 );} __int64 ans; int main(){ scanf("%d%d%d",&n,&m,&s); ans = 0; for(int i = 1; i <= n; i += 2){//enumerate hight for(int j = 1; j <= m && (r = s - i * j) >= 0; j += 2){ if(r == 0){//one rectangle is fairly enough //suppose (a,b) must be i,j //then (c,d) can have (i + 1)/2 * (j + 1)/2 choices //then (a,b) and (c,d) can exchange, so we * 2 //but if(a,b) and (c,d) are the same,exchange them does not make any difference //that is when a = c = i, b = d = j ans +=( (i + 1) * (j + 1) / 2 - 1) * f(i,j); }else for(int k = 1; k < j; k += 2) if(r % (2 * k) == 0 && i + r / k <= n) ans += 2 * f(i + r / k, j);// (a,b) and (c,d) can exchange } } printf("%I64d\n",ans); return 0; }