NOI2010 能量采集

wjh15101051's space

卧薪尝胆，厚积薄发。

NOI2010 能量采集

Date: Tue Jul 03 19:39:36 CST 2018

In Category: NoCategory

Description：

求 $\begin{align}2\times \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)-n\times m\end{align}$

$1\le n,m\le 100000$

Solution：

中心在于求 $\begin{align}\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)\end{align}$

$\begin{align}\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)\end{align}$

$\begin{align}=\sum_{i=1}^n\sum_{j=1}^mId(gcd(i,j))\end{align}$

$\begin{align}=\sum_{i=1}^n\sum_{j=1}^m\sum _{d|gcd(i,j)}\varphi(d)\end{align}$

$\begin{align}=\sum_{i=1}^n\sum_{j=1}^m\sum _{d|i,d|j}\varphi(d)\end{align}$

$\begin{align}=\sum_{d=1}^{min(n,m)}\varphi(d)\sum_{i=1,d|i}^n\sum_{j=1,d|j}^m1 \end{align}$

$\begin{align}=\sum_{d=1}^{min(n,m)}\varphi(d)\lfloor\frac n d\rfloor\lfloor\frac m d\rfloor\end{align}$

预处理欧拉函数前缀和 $+$ 除法分块

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

bool isprime[MAXN];

int prime[MAXN],tot = 0;

int phi[MAXN];

int main()

{

    scanf("%d%d",&n,&m);

    if(n > m)swap(n,m);

    for(int i = 2;i <= n;++i)

    {

        isprime[i] = true;

    }

    phi[1] = 1;

    for(int i = 2;i <= n;++i)

    {

        if(isprime[i])

        {

            prime[++tot] = i;

            phi[i] = i - 1;

        }

        for(int j = 1;j <= tot && i * prime[j] <= n;++j)

        {

            isprime[i * prime[j]] = false;

            if(i % prime[j] == 0)

            {

                phi[i * prime[j]] = phi[i] * prime[j];

                break;

            }

            else

            {

                phi[i * prime[j]] = phi[i] * phi[prime[j]];

            }

        }

    }

    long long res = 0;

    for(int i = 1;i <= n;++i)

    {

        res += (long long)phi[i] * (n / i) * (m / i);

    }

    cout << res * 2 - (long long)n * m << endl;

    return 0;

}

In tag: 数学-莫比乌斯反演

wjh15101051