HS
菜单
HS的博客
HDU4944 FSF’s game

题目链接

HDU

题目描述

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 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 2×2(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. (1×1 , 2×1, 2×2, 3×1, …, 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.

输入输出样例

输入 #1

3
1
3
100

输出 #1

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

说明/提示

In the second test case, there are six levels(1×1,1×2,1×3,2×2,2×3,3×3)
Here is the details for this game:
1×1: 1(K=1); 1×2: 2(K=1); 1×3: 3(K=1); 2×2: 2(K=1), 4(K=2); 2×3: 6(K=1); 3×3: 3(K=1), 9(K=3);
1+2+3+2+4+6+3+9=30

分析

网上的题解似乎没有几个使用纯粹的数论推柿子,于是写一下我的做法。

题目要求
$$
\sum_{i=1}^n\sum_{j=1}^i\sum_{k|gcd(i,j)}\frac{ij}{gcd(\frac{i}{k},\frac{j}{k})}
$$
直接化柿子。
$$
\sum_{i=1}^n\sum_{j=1}^i\sum_{k|gcd(i,j)}\frac{ij}{gcd(\frac{i}{k},\frac{j}{k})}
$$

首先对于每个$i$分别考虑。
$$
\sum_{j=1}^i\sum_{k|gcd(i,j)}\frac{ij}{gcd(\frac{i}{k},\frac{j}{k})}
$$

$$
i\sum_{k|i}k\sum_{j=1}^{\frac{i}{k}}\frac{j}{gcd(\frac{i}{k},j)}
$$

$$
i\sum_{k|i}k\sum_{j=1}^{\frac{i}{k}}\sum_{d|\frac{i}{k},d|j}[gcd(\frac{i}{k},j)==d]\frac{j}{d}
$$

$$
i\sum_{k|i}k\sum_{j=1}^{\frac{i}{k}}\sum_{d|\frac{i}{k},d|j}[gcd(\frac{i}{kd},\frac{j}{d})==1]\frac{j}{d}
$$

$$
i\sum_{k|i}k\sum_{d|\frac{i}{k}}\sum_{j=1}^{\frac{i}{kd}}[gcd(\frac{i}{kd},\frac{jd}{d})==1]\frac{jd}{d}
$$

$$
i\sum_{k|i}k\sum_{d|\frac{i}{k}}\sum_{j=1}^{\frac{i}{kd}}[gcd(\frac{i}{kd},j)==1]j
$$

$$
i\sum_{k|i}k\sum_{d|\frac{i}{k}}\frac{[\frac{i}{kd}==1]+\phi(\frac{i}{kd})}{2}
$$

$$
i\sum_{k|i}k\sum_{kd|i}\frac{[\frac{i}{kd}==1]+\phi(\frac{i}{kd})}{2}
$$

$$
i\sum_{p|i}\sum_{k|p}k\frac{[\frac{i}{p}==1]+\phi(\frac{i}{p})}{2}
$$

设$f(n)=\sum_{i|n}i$,$g(n)=\frac{[n==1]+\phi(n)}{2}$,$F=\sum_if(i)x^i$,$G=\sum_ig(i)x^i$。

则原式化为
$$
i\sum_{p|i}f(p)g(\frac{i}{p})
$$
由于$i$是常数项,可以以后再乘,只看后面的柿子$\sum_{p|i}f(p)g(\frac{i}{p})$。

设$h(n)=\sum_{p|h}f(p)g(\frac{i}{p})$,$H=\sum_ih(i)x^i$

只要求出$H$即可得到答案。
$$
H=F*G
$$
发现$H$其实是$F$和$G$的迪利克雷卷积,直接$O(nlogn)$暴力卷就行了。

最后$F$可以$O(nlogn)$预处理,$G$可以$O(n)$预处理。

总复杂度$O(nlogn)$。

一些对我而言的坑

不要忘了输出”Case”。

代码

#include<bits/stdc++.h>
using namespace std;
#define maxn 500010
#define lim 500000
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
    read(b...);
}
int T,prim[maxn],phi[maxn];
unsigned int F[maxn],G[maxn];
void init()
{
    phi[1]=2;
    for(int i=2;i<=lim;i++)
    {
        if(!prim[i])
        {
            prim[++prim[0]]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=prim[0]&&i*prim[j]<=lim;j++)
        {
            prim[i*prim[j]]=true;
            if(i%prim[j]==0)
            {
                phi[i*prim[j]]=phi[i]*prim[j];
                break;
            }
            phi[i*prim[j]]=phi[i]*(prim[j]-1);
        }
    }
    for(int i=1;i<=lim;i++)
        for(int j=i;j<=lim;j+=i)
            F[j]+=i;
    for(int i=1;i<=lim;i++)
    {
        unsigned int t=1ll*phi[i]*i>>1;
        for(int j=1;i*j<=lim;j++)
            G[i*j]+=t*F[j];
    }
    for(int i=2;i<=lim;i++)
        G[i]=G[i]*i+G[i-1];
}
int main()
{
    init();
    read(T);
    for(int i=1;i<=T;i++)
    {
        int x;
        read(x);
        printf("Case #%d: %un",i,G[x]);
    }
    return 0;
}

Gluttony

文章作者

发表评论

textsms
account_circle
email

HS的博客

HDU4944 FSF’s game
常见的欧拉函数变换+迪利克雷卷积
扫描二维码继续阅读
2020-03-03