Pairs
National Olympiad — Regional round (2010 season)
Submission name: pairs.cpp
Problem summary
Partition the integers 1 through 2n into unordered pairs so that every pair has the same positive difference. Count the possible partitions.
Input
One integer n.
Output
The number of partitions.
Constraints
1 < n < 5000000.
Worked example
Official statement example.
Input
3
Output
2
Solution analysis
- Fix the common difference d. Numbers with the same residue modulo d form a chain r,r+d,r+2d,… . Each chain must be paired along its edges. Its first element has only one available partner, so all pairs are forced and the chain length must be even.
- Write 2n=qd+r with 0≤r<d. If r is nonzero, the chains have lengths q and q+1, which cannot both be even. Thus d divides 2n and its quotient must be even. Equivalently d divides n.
- Every positive divisor of n therefore contributes exactly one partition. Count divisors in complementary pairs up to sqrt(n). For n=3 the divisors are 1 and 3, producing the two partitions in the statement.
Why it works
The chain argument proves necessity and uniqueness for each common difference. If d divides n, every residue chain has even length 2n/d and pairing consecutive members covers all numbers. Different differences yield different partitions; hence the answer equals the divisor count of n.
Complexity: O(sqrt(n)) time and O(1) space.
Watch out. Count a square-root divisor only once.,Differences need not be prime.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The chain argument proves necessity and uniqueness for each common difference. If d
// divides n, every residue chain has even length 2n/d and pairing consecutive members covers all
// numbers.
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int answer=0;
for(int d=1;d<=n/d;++d){
if(n%d==0){
answer+=(d==n/d?1:2);
}
}
cout<<answer<<'\n';
}