GP1 – Hardest SPOJ problem solved by me till date ;)

Problem Statement :
Geometric progression(GP) is a set in which the ratio of 2 consecutive numbers is same. for eg, 1,2,4,8,16…. In this the ratio of the numbers is 2.

The task here is very simple indeed.

You will be given the 3rd term , 3rd last term and the sum of the series. You need print length of the series & the series.

Input :

First line will contain a number indicating the number of test cases.

Each of the following t lines will have 3 number ’3term’ ,’3Lastterm’ and ‘sum’

3termĀ  – is the 3rd term in of the series and

3LasttermĀ  – is the 3rd term in of the series and

sum – is the sum of the series.

Output :

For each input of the test case, you need to print 2 lines.

fist line should have 1 value- number of terms in the series.

2nd line of the output should print the series numbers separated by single space

Example :

Input :
1
4 64 511
Output :

9
1 2 4 8 16 32 64 128 256

NOTE :

All the values will be in the range [0, 2^64] inclusive
The series will have at least 6 elements.
number of test cases <= 100.
The Ratio in all the cases will be an integer.
All the numbers will fit in 64 bits(long long in C)

Problem Link :
http://www.spoj.com/problems/GP1/

Source Code (C++) :

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int main () {
    unsigned long long t, x, y, s, a, r, n, i, p, term;
    cin >> t;
    while (t--) {
        cin >> x >> y >> s;
        i = 0;
        if (x == y) {
            r = 1;
            n = (unsigned long long)(s/x);
            cout << n << endl;
            while (i < n-1) {
                cout << x << " ";
                i++;
            }
            cout << x << endl;
        }

        else {
            if (s == 0) {
                s--;
            }
            p = (unsigned long long)(s/y);
            r = (unsigned long long)((-1+sqrt(1-4*(1-p)))/2.0);
            a = x/(r*r);
            n = (unsigned long long)(log (y/a)/log (r))+3;
            if (a*pow (r, n-2) == y) {
                n++;
            }
            cout << n << endl;
            term = 1;
            while (i < n-1) {
                cout << a*term << " ";
                term = term*r;
                i++;
            }
            cout << a*term << endl;
        }
    }
    return 0;
}

[fblike style="standard" showfaces="false" width="450" verb="like" font="arial"]
[fbshare type="button"]