HDU 4944 FSF’s gameの1本の良い問題
7850 ワード
FSF’s game
Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 727 Accepted Submission(s): 377
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
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
UESTC
标题:略.
考え方:A*B/gcd(A/k,B/k)についてはN*x/aと見なされ、xは未知であり、Nは既知であり、aはNの因子である.
(aは必ずNの因子なので)
1.今、私たちがこのように転化した後、1つ1つの列挙aを始めました.(私たちはaをgcd()の全体と見なした.)
2.決定されたa値についてaiと仮定すると、私たちが今しなければならないのは(N*x/a)要求を満たすxを見つけることです.
そしてそれに対してsum(xi/a)*Nを求和する.Nはずっと変わっていないからね.
このときa=gcd(N/k,x/k)は gcd(N,x) = k*a,
では、xの取値範囲については、[1,N]であり、gcd(N,x)=k*a(kは>0の正の整数)を求めることが知られている.
実は[1,N]の中で、aの倍数、a,2 a,3 a,4 a,,,,,N/a*a、正しいですか?
漏れないか、gcd()=k*aは、最大公約数がaの倍数であることを表す.
これでxに対して和を求めます.sum = a(1+2...N/a) = a*(1+N/a)*N/a/2 =>(1+N/a)*N/2;
最後に式A*x/aによって、 (1+N/a)*N/a/2 * N;
フィルタリング、dpでいいです.
Time Limit: 9000/4500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 727 Accepted Submission(s): 377
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
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
UESTC
标题:略.
考え方:A*B/gcd(A/k,B/k)についてはN*x/aと見なされ、xは未知であり、Nは既知であり、aはNの因子である.
(aは必ずNの因子なので)
1.今、私たちがこのように転化した後、1つ1つの列挙aを始めました.(私たちはaをgcd()の全体と見なした.)
2.決定されたa値についてaiと仮定すると、私たちが今しなければならないのは(N*x/a)要求を満たすxを見つけることです.
そしてそれに対してsum(xi/a)*Nを求和する.Nはずっと変わっていないからね.
このときa=gcd(N/k,x/k)は gcd(N,x) = k*a,
では、xの取値範囲については、[1,N]であり、gcd(N,x)=k*a(kは>0の正の整数)を求めることが知られている.
実は[1,N]の中で、aの倍数、a,2 a,3 a,4 a,,,,,N/a*a、正しいですか?
漏れないか、gcd()=k*aは、最大公約数がaの倍数であることを表す.
これでxに対して和を求めます.sum = a(1+2...N/a) = a*(1+N/a)*N/a/2 =>(1+N/a)*N/2;
最後に式A*x/aによって、 (1+N/a)*N/a/2 * N;
フィルタリング、dpでいいです.
1 #include<iostream>
2 #include<stdio.h>
3 #include<cstring>
4 #include<cstdlib>
5 using namespace std;
6 typedef __int64 LL;
7
8 const int maxn = 5e5+3;
9 LL p = 1;
10 LL dp[maxn];
11 void init()
12 {
13 int j,tmp;
14 for(j=1;j<=32;j++)p=p*2;
15
16 for(int i=1;i<maxn;i++){
17 tmp = i;
18 for(j=1;(tmp=i*j)<maxn;j++){
19 dp[tmp]=(dp[tmp]+((LL)(1+j)*(LL)j)/2)%p;
20 }
21 }
22 dp[1]=1;
23 for(int i=2;i<maxn;i++){
24 dp[i]=(dp[i-1]+dp[i]*i)%p;
25 }
26 }
27 int main()
28 {
29 int T,n;
30 init();
31 scanf("%d",&T);
32 for(int t=1;t<=T;t++)
33 {
34 scanf("%d",&n);
35 printf("Case #%d: %I64d
",t,dp[n]);
36 }
37 return 0;
38 }