SQMA06--Editorial

editorial
1

PROBLEM NAME:

A P

PROBLEM LINK:

DIFFICULTY

EASY

PREREQUISITES:

MATH , ARITHMETIC PROGRESSION

PROBLEM:

Given an integer N find arithmetic progressions consisting of integers with a common difference of 1 have a sum of N ?

SOLUTION:

The sum S of an arithmetic sequence with first term a, n terms, and common difference 1 can be found with the formula S=n/2[2a+nāˆ’1]. Rearranging this and multiplying across by 2, we get 2S=n(n+2aāˆ’1), therefore n must be a factor of 2S, which is 2N in this problem. Rearranging further, we get a=((2N/i)āˆ’i+1)/2. Now, we can iterate over all the factors i of 2N, and we need to check if (2N/i)āˆ’i+1 is divisible by 2.

Time complexity: O(āˆšN)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n,ans=0;
    cin>>n;
    for (ll i=1;i*i<=2*n;++i)
    {
        if ((2*n)%i==0)
        {
            if (((2*n/i)-i+1)%2==0)
                ++ans;
            if (i*i!=2*n&&(i-(2*n/i)+1)%2==0)
                ++ans;
        }
    }
    cout<<ans;
    return 0;
}
2

Hi, can you please tell for sample tc, how does [1, 2] satisfy the condition. 1+2 =3 which is not equal to N(N=12) ?

3

it was a mistake in sample input insted of [1,2] it is [12]

4

But we cant form an AP with 1 element. We need atleast 2 terms.

1 Like