Proficient.
Put your skills to the test.

Problem summary

A ram begins in the bottom-left cell of an M-row, N-column unit-cell pen. It alternates right and up moves, breaking one fence per move until it exits. Given K unbroken fences, list every possible dimension pair.

Constraints

3 ≤ K ≤ 10^9; M,N positive.

Worked example

An independently prepared example for this explanation.

14

2
1 5
3 2

Solution analysis

1. The pen initially has 2MN+M+N fences. If N≤M, the rightward exit happens after 2N−1 moves, leaving K=(2N+1)M−N+1. Otherwise the upward exit occurs after 2M moves, leaving K=(2M+1)N−M.
2. Enumerate the smaller dimension s, bounded by √K. In the first case set N=s and solve M=(K+s−1)/(2s+1), checking integrality and M≥s. In the second set M=s and solve N=(K+s)/(2s+1), checking integrality and N>s.
3. For K=14, N=2 yields M=3 in the first case; M=1 yields N=5 in the second. Sorting by rows produces (1,5),(3,2). The strict and nonstrict inequalities keep square pens in only one case.

Why it works

The move count follows directly from which coordinate reaches its boundary first. Subtracting that count yields the two displayed equations. Every valid pen belongs to exactly one case, with a smaller dimension at most √K. Enumeration solves the corresponding linear equation and checks all necessary conditions, so it lists all and only valid pairs.

Watch out. M is the row count. The rightward move happens first; this creates different formulas on the two sides of M=N. Use 64-bit arithmetic.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: The pen initially has 2MN+M+N fences.
using namespace std;
int main(){
    long long k;
    cin>>k;
    vector<pair<long long,long long>>answers;
    for(long long s=1;s*s<=k;++s){
        long long divisor=2*s+1;
        if((k+s-1)%divisor==0){
            long long rows=(k+s-1)/divisor;
            if(rows>=s){
                answers.push_back({rows,s});
            }
        }
        if((k+s)%divisor==0){
            long long columns=(k+s)/divisor;
            if(columns>s){
                answers.push_back({s,columns});
            }
        }
    }
    sort(answers.begin(),answers.end());
    cout<<answers.size()<<'\n';
    for(auto answer:answers){
        cout<<answer.first<<' '<<answer.second<<'\n';
    }
}