一个长方形可以由多个正方形组成，然后题目要求根据输入的长方形内部的正方形的总数，来求得有多少个长方形（正方形是特殊的长方形）满足这类条件，并且输出对应的长和宽。
假设正方形单位长度为1，长为m宽为n的长方形,令n<=m,其内部有的正方形总数为: t = m*n + (m-1)*(n-1) + (m-2)*(n-2) + ......+1*(n-m+1) = m*m*n - (m+n)*m*(m-1)/2 + (m-1)*m*(2*m-1)/6;
m*m*n可以由公式化开，将m*n凑在一起，总共有m个m*n;
- (m+n)*m*(m-1)/2由-(m+n)-2(m+n)-......-(m-1)(n+m)再由等差公式得出;
(m-1)*m*(2*m-1)/6 由1 + 4 + 9 +......+(m-1)^2 带入平方和的前a项和 Sa = a*(a+1)*(2*a+1)/6得出；
最后由化简成的公式可以看出三个未知数求出两个，最后一个必然也求的出;
代码中写的时候把行当成m了，列是n，到了行大于列的时候停止;
YY 想找出所有的 <n,m>正整数对使得 n 行 m 列的表格中恰好包含 t 个正方形。
输入一行，包含一个正整数 t。(1≤t≤10的18次方)(1≤t≤10的18次方)
第一行输出一个整数 z，表示 <n,m> 对的个数。
接下来包含 z 行，每行两个正整数 n,m，以空格分隔，表示 n 行 m 列的表格中恰好包含 t 个正方形。
注意：输出 <n,m> 对时，以 n 递增的顺序输出，n 相同时以 m 递增的顺序输出。
1行8列、2行3列、3行2列、8行1列的表格均恰好包含8个正方形
下图以2行3列为例：
#include<stdio.h> #include<iostream> #define Maxn 1000 using namespace std; #define c cout //定义输出 #define e endl //定义换行 long long int func(long long int m,long long int n,long long int t){//不断筛选合适的loc，返回 int flag = 1; long long int loc=n,lef=m,rig=n,x=0; while(1){ x = m*(m+1)*(3*loc+1-m)/6; if(lef==rig&&x!=t){//没有值可以二分并且计算出的结果与t不符，返回 return 0; } if(lef+1==rig&&x!=t){//lef和rig的值恰好相隔1，并且两个指标带入loc，得出的x的值位于t两边，返回 return 0; } if(x==t)//找到想要的loc，返回，否则不断缩小二分区间 return loc; else if(x>t){ rig = loc; loc = (rig+lef)/2; }else{ lef = loc; loc = (rig+lef)/2; } } if(!flag) return 0; } int main(){ long long int m=1,n=0,x=0,t=0; long long mi[Maxn],ni[Maxn]; while(scanf("%lld",&t)!=EOF){ int count=1; m=1,x=0; n = t; while(1){ n = (t*6/(m*(m+1))+m-1)/3;//m每次自加，n的范围也要对应的缩小，不能整除的话n会偏小(不能整除那就说明这个m和n的组合是不能推出t的)，传入func以后得出来的值一定不会超过t //相反的，能整除，实际上也说明这个n值就是所求的n值。 将其带入func，第一步就能运算得出所要的loc并且返回 //带入func更多的只是为了验算 x = func(m,n,t); if(m>n) break; if(x){ n = x; mi[count] = m; ni[count++] = n; } m++; } count-=1; if(ni[count]!=mi[count]){ c<<2*count<<e; for(int i=1;i<=count;i++) c<<mi[i]<<" "<<ni[i]<<e; for(int i=count;i>0;i--) c<<ni[i]<<" "<<mi[i]<<e; }else { c<<2*count-1<<e; for(int i=1;i<=count;i++) c<<mi[i]<<" "<<ni[i]<<e; for(int i=count-1;i>0;i--) c<<ni[i]<<" "<<mi[i]<<e; } } return 0; }
