首页 > 代码库 > HDU 4944
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)
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).
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.
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
题意:很容易了 ,求 : A*B/gcd(A/K,B/K) 的值。
sl :很容易知道 k必须是 a,b 的因子。然后A B 设 C=gcd(A,B)/k . 可以知道 C为gcd(A,B)的所有因子。 求gcd(i,n) 的因子等价于先筛出所有n的因子。
然后由于 因子 能整除i 所以 i 必然是 1*k,2*k,3*k,4*k......n*k . 所以所有的 因子为 i的和为 (1+2+3+4+、、、+n/i) .剩下的dp能搞了。。。。。
orz推出来的神犇 ,杂家不会啊。悲伤。。。
1 // by caonima
2 // hehe
3 #include <cstdio>
4 #include <cstring>
5 #include <algorithm>
6 #include <vector>
7 #include <map>
8 using namespace std;
9 typedef long long LL;
10 const int MAX = 500000+10;
11 const LL MOD = 1LL<<32;
12 LL dp[MAX],ans[MAX];
13 void gao1() {
14 for(int i=1;i<MAX;i++) {
15 for(int j=i;j<MAX;j+=i) {
16 ans[j]+=(LL)(j/i+1)*(j/i)/2LL;
17 }
18 }
19 }
20 void init() {
21 memset(dp,0,sizeof(dp)); dp[1]=1;
22 for(int i=2;i<MAX;i++) {
23 dp[i]=(dp[i-1]+(LL)ans[i]*(LL)i)%MOD;
24 }
25 }
26 int main() {
27 //printf("%I64d\n",MOD);
28 int cas,n,cnt=0;
29 gao1(); init();
30 scanf("%d",&cas);
31 while(cas--) {
32 scanf("%d",&n);
33 printf("Case #%d: %I64d\n",++cnt,dp[n]);
34 }
35 return 0;
2 // hehe
3 #include <cstdio>
4 #include <cstring>
5 #include <algorithm>
6 #include <vector>
7 #include <map>
8 using namespace std;
9 typedef long long LL;
10 const int MAX = 500000+10;
11 const LL MOD = 1LL<<32;
12 LL dp[MAX],ans[MAX];
13 void gao1() {
14 for(int i=1;i<MAX;i++) {
15 for(int j=i;j<MAX;j+=i) {
16 ans[j]+=(LL)(j/i+1)*(j/i)/2LL;
17 }
18 }
19 }
20 void init() {
21 memset(dp,0,sizeof(dp)); dp[1]=1;
22 for(int i=2;i<MAX;i++) {
23 dp[i]=(dp[i-1]+(LL)ans[i]*(LL)i)%MOD;
24 }
25 }
26 int main() {
27 //printf("%I64d\n",MOD);
28 int cas,n,cnt=0;
29 gao1(); init();
30 scanf("%d",&cas);
31 while(cas--) {
32 scanf("%d",&n);
33 printf("Case #%d: %I64d\n",++cnt,dp[n]);
34 }
35 return 0;
36 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。