D. Spongebob and Squares
Spongebob is already tired trying to reason his weird actions and calculations, so he simply asked you to find all pairs of n and m, such that there are exactly x distinct squares in the table consisting of n rows and m columns. For example, in a 3 × 5 table there are 15squares with side one, 8 squares with side two and 3 squares with side three. The total number of distinct squares in a 3 × 5 table is15 + 8 + 3 = 26.
Input
The first line of the input contains a single integer x (1 ≤x≤ 1018) — the number of squares inside the tables Spongebob is interested in.
Output
First print a single integer k — the number of tables with exactly x distinct squares inside.
Then print k pairs of integers describing the tables. Print the pairs in the order of increasing n, and in case of equality — in the order of increasing m.
Sample test(s)
input
26
output
6
1 26
2 9
3 5
5 3
9 2
26 1
input
2
output
2
1 2
2 1
input
8
output
4
1 8
2 3
3 2
8 1
来自 <http://codeforces.com/problemset/problem/599/D>
Codeforces Round #332 (Div. 2)
【题意】：
对于给定的X，找出所有的 M*N 矩阵，使得其中恰含 X 个正方形
【解题思路】：
主要是推公式。
对于给定的M N：
S = M*N + (M-1)*(N-1) + …… 直至其中一项变0；
以上公式展开并求和可得：
而右边这几项都可以直接求出，
X = m*n*b - (m+n)*(m-1)*m/2 + (2*m-1)*m*(m-1)/6;（m<n）
可知上述 N 可用X和M来线性表示：
故枚举其中一项，利用公式求另一项即可；
注意还要判重和排序，这里直接用set就可以了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<vector> 6 #include<algorithm> 7 #include<set> 8 #define inf 0x3f3f3f3f 9 #define LL long long 10 #define maxn 2100000 11 #define IN freopen("in.txt","r",stdin); 12 using namespace std; 13 14 LL sum; 15 LL a, b; 16 struct node{ 17 LL a,b; 18 node(LL _a,LL _b) {a=_a;b=_b;} 19 bool operator <(const node& c)const{ 20 return a<c.a||a==c.a&&b<c.b; 21 } 22 }; 23 set<node> ans; 24 25 LL check(LL a, LL b) 26 { 27 return a*a*b - (a+b)*(a-1)*a/2 + (2*a-1)*a*(a-1)/6; 28 } 29 LL cal(LL a) 30 { 31 return (6*sum-a+a*a*a)/(3*a*a+3*a); 32 } 33 34 int main(int argc, char const *argv[]) 35 { 36 //IN; 37 38 while(scanf("%I64d",&sum)!=EOF) 39 { 40 ans.clear(); 41 for(a=1; a<=maxn; a++) { 42 b = cal(a); 43 44 if(check(min(a,b),max(a,b)) != sum) continue; 45 46 ans.insert(node(a,b)); 47 if(a!=b) ans.insert(node(b,a)); 48 } 49 50 int cnt = ans.size(); 51 //sort(ans.begin(),ans.end()); 52 printf("%d\n",cnt); 53 set<node>::iterator it; 54 for(it=ans.begin();it!=ans.end();it++){ 55 printf("%I64d %I64d\n",(*it).a,(*it).b); 56 } 57 } 58 59 return 0; 60 }
Codeforces 599D Spongebob and Squares（数学）
原文：http://www.cnblogs.com/Sunshine-tcf/p/5007782.html