HDOJ 4944 FSF’s game

http://blog.csdn.net/keshuai19940722/article/details/38519681
真相を知らないでください。。。。
FSF’s game
Time Limit：9000/4500 MS（Java/Others）    Memory Limit:13131313137272 K(Java/Others)Total Submission(s):448    Acceepted Submission(s)：215
Problem Description
FSF has programmed a game.
In this game，plyers 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、playrs can get some coins.
If plears success fully divide a AxB rectangle(length:A，width:B)into KxKスクウェア(side length:K)、they can get A*B/gcd(A/K，B/K)ゴールドCoins.
In a level，you can’t get coins twice with same method. 
（For example、You can get 6 coins from 2 x 2（A=2、B=2）rectanle.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；
The re are N*(N＋1)/2 levels in this game，and everry level is an unique rectangle.(1 x 1,2 x 1,2 x 2,3 x 1，…，Nx(N-1)，NxN)
FSF has playd this game for a long time，and he finally gets all the coins in the game.
Unfortunally、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
The re are multiplly test cases.
The first line contains an integer T(T<=500000)、the number of test cases
Each of the next T LINE contain an integer N（N<=500000）.
 
Output
Output a single line for each test case.
For each test case，you Shouuld output「Case((zhi C)」.first，where C indicates the case number and counts from 1. 
The n output the answer，the value of that UNSIGN ED 32-BIT INTEGER variable.
 
Sample Input

   
   
   
   

    
    
    
    3
1
3
100
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    Case #1: 1
Case #2: 30
Case #3: 15662489


    
    
    
    
 
     
 
      Hint 
     
In 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 
    
    
    
    
     
   
   
   
   

 
Author
USTC
 
ソurce
2014 Multi-University Training Conteest 7
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long int LL;

const int maxn=500050;
const LL mod=1LL<<32;

LL f[maxn],s[maxn];

void init()
{
    for(int i=1;i<maxn;i++)
    {
        for(int k=1;k*i<maxn;k++)
        {
            f[i*k]+=(1LL+k)*k/2;
            f[i*k]%=mod;
        }
        f[i]=f[i]*i;
        f[i]%=mod;
    }
    for(int i=1;i<maxn;i++)
    {
        s[i]=(f[i]+s[i-1])%mod;
    }
}

int main()
{
    init();
    int T_T,cas=1;
    scanf("%d",&T_T);
    while(T_T--)
    {
        int x;
        scanf("%d",&x);
        printf("Case #%d: %lld
",cas++,s[x]);
    }
    return 0;
}