D. Spongebob and Squares

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/599/problem/D

Description

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 Input

26

Sample Output

6 1 26 2 9 3 5 5 3 9 2 26 1

HINT

 

题意

给你x，然后让你找有多少个n*m的矩形，可以由x个相同的多边形组成

题解：

数学题，这道题实际上是问，f(n,m) = sigma(k=1,k=min(n,m))(n-k+1)*(m-k+1)=x的解有多少个

化简之后，我们可以得到f(n,m) = n^2m+n^2+n*m+n-(n+1)*n/2*(n+m+2)+n*(n+1)*(2n+1)/6

这个式子是一个关于m的一次函数，我们枚举n就好了

就可以求m了，注意break条件

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct node{    long long x,y;};bool cmp(node a,node b){    return a.y>b.y;}vector
         
           ans1;int main(){    long long x;cin>>x;    for(long long i = 1;i<=10000000LL||i*i*i<=x;i++)    {        long long a = (i*i+i-(i+1)*i/2LL);        long long b = (i*i+i-(i+1)*i*i/2LL-(i+1)*i+(i*(i+1)*(2*i+1)/6));        long long y = x;        long long t= (y-b)/a;        if(i>t)continue;        if(a*t+b==y)        {            if(i==t)            {                node k;k.x = i,k.y = t;                ans1.push_back(k);            }            else            {                node k;k.x = i,k.y = t;                ans1.push_back(k);                k.x = t,k.y = i;                ans1.push_back(k);            }        }    }    sort(ans1.begin(),ans1.end(),cmp);    printf("%d\n",ans1.size());    for(int i=0;i
         
        
       
      
     

 

代码