Intermediate.
Put your skills to the test.

Problem summary

A number’s beauty is its number of representations as a sum of consecutive positive integers, including the one-term sum. Choose the most beautiful input number, breaking ties by smaller value.

Constraints

2 ≤ n ≤ 1000; 1 ≤ a[i] ≤ 2×10^9.

Worked example

Input and output for the worked example discussed below.

2
15 30

15 4

Solution analysis

1. A classical counting identity says that the number of consecutive-positive-sum representations of x equals the number of odd divisors of x. Remove all factors of 2, factor the remaining odd part, and multiply exponent+1 for its distinct prime factors.
2. To see the identity, fix an odd divisor d of x. A d-term sequence centred at x/d has sum x. If its first term is positive, keep it; otherwise the complementary even length 2x/d gives the corresponding positive sequence. Exactly one of these two choices starts positively.
3. For 15, the odd divisors are 1,3,5,15, so beauty is 4: 15; 7+8; 4+5+6; 1+2+3+4+5. The number 30 has the same odd divisors, so the tie selects 15.

Why it works

For a length k representation, 2x=k(2a+k−1) with a≥1. The two factors have opposite parity; their odd factor determines one odd divisor d of x. Conversely the odd/even complementary lengths associated with d produce exactly one positive starting term. This bijection proves the divisor count. The comparison then implements the required maximum-beauty/minimum-value ordering.

Watch out. Only odd divisors matter. Include the number itself as a one-term representation. Update the chosen value on equal beauty when the new value is smaller.

An independently written complete program with standard headers.

#include<iostream>
using namespace std;
int beauty(long long value){
    while(value%2==0){
        value/=2;
    }
    int result=1;
    for(long long prime=3;prime*prime<=value;prime+=2){
        int exponent=0;
        while(value%prime==0){
            value/=prime;
            exponent++;
        }
        // Each exponent can range independently from zero to its full value.
        result*=exponent+1;
    }
    if(value>1){
        result*=2;
    }
    return result;
}
int main(){
    int n;
    cin>>n;
    long long best=0;
    int bestBeauty=-1;
    for(int i=0;i<n;i++){
        long long value;
        cin>>value;
        int current=beauty(value);
        if(current>bestBeauty||(current==bestBeauty&&value<best)){
            best=value;
            bestBeauty=current;
        }
    }
    cout<<best<<' '<<bestBeauty<<'\n';
}