— 数论 — 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 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.
UESTC
2014 Multi-University Training Contest 7
We have carefully selected several similar problems for you: 4943 4942 4941 4940 4939 N(LogN)的复杂度。