Skip to content

Kevin's Home

HDU4944 FSF’s game

数论1 min read

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.

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 AB/ 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, AB/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.

Sample Input

Sample Output





2014 Multi-University Training Contest 7


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