Skip to content## HDU4944 FSF’s game

Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 166 Accepted Submission(s): 76## Problem Description FSF has programmed a game. In this game, players need to divide a rectangle into several same squares. The length and width of rectangles are integer, and of course the side length of squares are integer.## Input

## Output

## Sample Input

## Sample Output

### Hint

## Author

## Source

## Recommend

— 数论 — 1 min read

After division, players can get some coins.
If players successfully divide a AxB rectangle(length: A, width: B) into KxK squares(side length: K), they can get A*B/ gcd(A/K,B/K) gold coins.
In a level, you can’t get coins twice with same method.
(For example, You can get 6 coins from 2x2(A=2,B=2) rectangle. When K=1, A*B/gcd(A/K,B/K)=2; When K=2, A*B/gcd(A/K,B/K)=4; 2+4=6; )

There are N*(N+1)/2 levels in this game, and every level is an unique rectangle. (1x1 , 2x1, 2x2, 3x1, ..., Nx(N-1), NxN)

FSF has played this game for a long time, and he finally gets all the coins in the game. Unfortunately ,he uses an UNSIGNED 32-BIT INTEGER variable to count the number of coins. This variable may overflow. We want to know what the variable will be. (In other words, the number of coins mod 2^32)

There are multiply test cases.

The first line contains an integer T(T<=500000), the number of test cases

Each of the next T lines contain an integer N(N<=500000).

Output a single line for each test case.

For each test case, you should output "Case #C: ". first, where C indicates the case number and counts from 1.

Then output the answer, the value of that UNSIGNED 32-BIT INTEGER variable.

UESTC

2014 Multi-University Training Contest 7

We have carefully selected several similar problems for you: 4943 4942 4941 4940 4939 N(LogN)的复杂度。