[原创]hdu 6134 Battlestation Operational [反演]【数学】

2017-08-18 01:01:18 Tabris_ 阅读数：429

博客爬取于2020-06-14 22:39:28
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/77349012

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6134
———————————————————————————————————————————
Battlestation Operational

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 187 Accepted Submission(s): 100

Problem Description

The Death Star, known officially as the DS-1 Orbital Battle Station, also known as the Death Star I, the First Death Star, Project Stardust internally, and simply the Ultimate Weapon in early development stages, was a moon-sized, deep-space mobile battle station constructed by the Galactic Empire. Designed to fire a single planet-destroying superlaser powered by massive kyber crystals, it was the pet project of the Emperor, Darth Vader, and its eventual commander Grand Moff Wilhuff Tarkin to expound the military philosophy of the aptly named Tarkin Doctrine.

— Wookieepedia

In the story of the Rogue One, the rebels risked their lives stolen the construction plan of the Death Star before it can cause catastrophic damage to the rebel base. According to the documents, the main weapon of the Death Star, the Superlaser, emits asymmetric energy in the battlefield that cause photons to annihilate and burns everything in a single shot.

You are assigned the task to estimate the damage of one shot of the Superlaser.

Assuming that the battlefield is an n×n grid. The energy field ignited by the Superlaser is asymmetric over the grid. For the cell at i-th row and j-th column, ⌈i/j⌉ units of damage will be caused. Furthermore, due to the quantum effects, the energies in a cell cancel out if gcd(i,j)≠1 or i< j.

The figure below illustrates the damage caused to each cell for n=100. A cell in black indicates that this cell will not be damaged due to the quantum effects. Otherwise, different colors denote different units of damages.

Your should calculate the total damage to the battlefield. Formally, you should compute

f(n)=∑i=1n∑j=1i⌈ij⌉[(i,j)=1]f(n)=∑_{i=1}^n∑_{j=1}^i⌈\frac{i}{j}⌉[(i,j)=1],

where [(i,j)=1] evaluates to be 1 if gcd(i,j)=1, otherwise 0.

Input
There are multiple test cases.

Each line of the input, there is an integer n (1≤n≤106), as described in the problem.

There are up to 104 test cases.

Output
For each test case, output one integer in one line denoting the total damage of the Superlaser, f(n) mod 109+7.

Sample Input
1
2
3
10

Sample Output
1
3
8
110

Source
2017 Multi-University Training Contest - Team 8
———————————————————————————————————————————
题意：给你一个n让你计算f(n)=∑i=1n∑j=1i⌈ij⌉[(i,j)=1]f(n)=∑_{i=1}^n∑_{j=1}^i⌈\frac{i}{j}⌉[(i,j)=1],

考虑$ g[i] = ∑_{j=1}^i⌈\frac{i}{j}⌉,h[i]=∑_{j=1}^i⌈\frac{i}{j}⌉[(i,j)=1],f[n]=\sum_{i=1}^nh[i]$

显然有

g[i]=∑d∣ih[id]反演得h[i]=∑d∣iμ(d)g[id]g[i]=\sum_{d|i}h[\frac{i}{d}] \\ 反演得 \\h[i]=\sum_{d|i} \mu(d)g[\frac{i}{d}]

所以得到g[i]g[i]后,可以通过筛法计算出h[i]h[i],然后前缀和处理一下就得到了f[i]f[i]

所以问题就是如何求g[i]g[i],
很显然 枚举ii 有nnn\sqrt{n}的做法求出来,但是有点爆啊

所以这里采取枚举jj的做法,
有g[j]=1,g[j+1,j∗2]=2,g[j∗2+1,j∗3]=3,...,g[j∗k+1,n]=k+1g[j]=1,g[j+1,j*2]=2,g[j*2+1,j*3]=3,...,g[j*k+1,n]=k+1

转化一下,就是
g[j,n]+=1,g[j+1,n]+=1,g[j∗2+1,n]+=1,...,g[j∗k+1,n]+=1g[j,n] +=1,g[j+1,n]+=1,g[j*2+1,n]+=1,...,g[j*k+1,n]+=1

所以在每个+1+1开始的位置加上1,然后前缀和处理一下就行了

我这里写的麻烦了,其实不用把mu[]mu[]求出来,直接计算就行.

附本题代码
———————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int n;
LL g[N],f[N];
int mu[N],prime[N],vis[N],cnt;
void Init()
{
    memset(vis,0,sizeof(vis));
    mu[1] = 1;
    cnt = 0;
    for(int i=2; i<N; i++)
    {
        if(!vis[i])
        {
            prime[cnt++] = i;
            mu[i] = -1;
        }
        for(int j=0; j<cnt&&i*prime[j]<N; j++)
        {
            vis[i*prime[j]] = 1;
            if(i%prime[j]) mu[i*prime[j]] = -mu[i];
            else
            {
                mu[i*prime[j]] = 0;
                break;
            }
        }
    }
}

int main(){
    Init();
    for(int i=1;i<N;i++){
        g[i]++;
        for(int j=i;j<N;j+=i) g[j+1]++;
    }
    for(int i=1;i<N;i++) g[i]+=g[i-1];

    for(int i=1;i<N;i++)
        for(int j=i;j<N;j+=i)
            f[j]=(f[j]+mu[i]*g[j/i])%MOD;

    for(int i=1;i<N;i++) f[i]=(f[i]+f[i-1])%MOD;

    while(~scanf("%d",&n)) printf("%lld\n",f[n]);

    return 0;
}