HDU - 4944 FSF’s game
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 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)
Input
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
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
3
1
3
100
Sample Output
Case #1: 1
Case #2: 30
Case #3: 15662489
HintIn the second test case, there are six levels(1x1,1x2,1x3,2x2,2x3,3x3)
Here is the details for this game:
1x1: 1(K=1); 1x2: 2(K=1); 1x3: 3(K=1); 2x2: 2(K=1), 4(K=2); 2x3: 6(K=1); 3x3: 3(K=1), 9(K=3);
1+2+3+2+4+6+3+9=30
題意：給你個n，讓你求在n的范圍內，能否將一個矩形分成若干個相同大小為k的正方形，對應有val值，讓你統計在n內的所有可能的分數總值
思路：首先我們來試著求解∑(n*i)/(gcd(n/k, i/k)) {1<=i <= n} ，那麼我們可以確定的是如果可以把n*m的矩形分成大小為k的正方形的話，那麼k一定是gcd(n, i)的因子，那麼對於一項來說因為公式可以變形為(n*i*k)/gcd(n, i) -> n*(i/c1 + i/c2 + ...) {k枚舉所有的可能}，
就拿6*1, 6*2, 6*3, 6*4, 6*5, 6*6來說，對應的k依次有
1；1、2； 1、3；1、2；1；1，2，6，那麼cj是n的因子，那麼i/cj就是因子對應的系數，我們再從所有的i來講，對於因子cj我們可以計算出所有可能的數，比如因子cj,我們可以得到cj, 2*cj, 3*cj, 4*cj....n，那麼對應的系數就是我們需要的i/cj,累加起來計算是:
num[cj] = (1+2+...+n/cj)=(1+n/cj)*(n/cj)/2，然後最後是遞推：
ans[n]=ans[n-1]+val[n] {val[n]=∑num[cj] {1<=i <= n}}
#include
#include
#include
#include
#define ll __int64
using namespace std;
const int maxn = 500005;
const ll mod = 1ll<<32;
ll num[maxn], dp[maxn];
void cal() {
for (ll i = 1; i < maxn; i++)
for (ll j = i; j < maxn; j += i)
num[j] += (j/i+1) * (j/i) / 2;
}
void init() {
memset(num, 0, sizeof(num));
cal();
dp[1] = 1;
for (ll i = 2; i < maxn; i++) {
dp[i] = dp[i-1] + num[i]*i;
dp[i] = dp[i] % mod;
}
}
int main() {
init();
int t, n, cas = 1;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
printf("Case #%d: %I64d\n", cas++, dp[n]);
}
return 0;
}
