Alien Generator Solution Google Kickstart 2021

Table of Contents

Problem

Astronauts have landed on a new planet, Kickstartos. They have discovered a machine on the planet: a generator that creates gold bars. The generator works as follows. On the first day, an astronaut inputs a positive integer KK into the generator. The generator will produce KK gold bars that day. The next day, it will produce K+1K+1, the following day, K+2K+2, and so on. Formally, on day ii, the generator will produce K+i−1K+i−1 gold bars.

However, the astronauts also know that there is a limitation to the generator:
if on any day, the generator would end up producing more than GG gold bars in total across all the days, then it will break down on that day and will produce 00 gold bars on that day and thereafter. The astronauts would like to avoid this, so they want to produce exactly GG gold bars.

Consider K=2K=2 and G=8G=8. On day 11, the generator would produce 22 gold bars. On day 22, the generator would produce 33 more gold bars making the total gold bars is equal to 55. On day 33, the generator would produce 44 more gold bars which would lead to a total of 99 gold bars. Thus, the generator would break on day 33 before producing 44 gold bars. Hence, the total number of gold bars generated is 55 in this case.

Formally, for a given GG, astronauts would like to know how many possible values of KK on day 11 would eventually produce exactly GG gold bars.

Input

The first line of the input gives the number of test cases, TT. TT lines follow.
Each line contains a single integer GG, representing the maximum number of gold bars the generator can generate.

Output

For each test case, output one line containing Case #xx: yy, where xx is the test case number (starting from 11) and yy is the number of possible values of KK on day 11 that would eventually produce exactly GG gold bars.

Limits

Time limit: 30 seconds.
Memory limit: 1 GB.
1≤T≤1001≤T≤100

Test Set 1

1≤G≤1041≤G≤104.

Test Set 2

1≤G≤10121≤G≤1012 for at most 2020 test cases.
For the remaining cases, 1≤G≤1041≤G≤104.

Sample

Sample Input

2
10
125

Sample Output

Case #1: 2
Case #2: 4

For Sample Case #1, there are 22 possible values of KK (1,10)(1,10) that would eventually produce exactly 1010 gold bars. For K=1K=1, we will have 1+2+3+4=101+2+3+4=10 gold bars after 44 days, and for K=10K=10, we will have 1010 gold bars after just 11 day.

For Sample Case #2, there are 44 possible values of KK (8,23,62,125)(8,23,62,125) that would eventually produce exactly 125125 gold bars.

Also Read:

Solution:

#include<cstdio>
long long int g;
int main() {
	int tcn;
	scanf("%d", &tcn);
	for (int tc = 1; tc <= tcn; tc++) {
		scanf("%lld", &g);
		int ans = 0;
		for (long long int i = 1;; i++) {
			long long int r = i * (i + 1) / 2;
			if (r > g)break;
			if ((g - r) % i == 0)ans++;
		}
		printf("Case #%d: %d\n", tc, ans);
	}
	return 0;
}

Alien Generator Solution Google Kickstart 2021