BZOJ2005 [NOI2010]能量采集

2014.12.10 08:05 Wed| 2 visits oi_2015| 2015_刷题日常| Text

NOI的水原来在四年前就有所体现了。线性筛欧拉函数?怎么可能是这种“高级”的东西!

Solution

解决这道题其实只需要类似于容斥原理的思想就好了啦……

题意即求出 $\sum\limits {i=1} ^n\sum\limits _{j=1} ^m \gcd (i,j) \times 2-1$

设 $f[i]$ 表示最大公约数为 $i$ 的数对的个数。则 $f[i]= \lfloor n/i \rfloor \times \lfloor m/i \rfloor-\sum\limits{j=2}^{\lfloor\min(n,m) /i\rfloor}f[i·j]$ 。从后向前计算一遍 $f$ 数组即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005

long long n,m,ans,f[N];

int main()
{
    cin>>n>>m;
    for(long long i=min(n,m);i;i--)
    {
        f[i]=(n/i)*(m/i);
        for(long long j=2;i*j<=min(n,m);j++)
            f[i]-=f[i*j];
    }
    for(long long i=min(n,m);i;i--)
        ans+=f[i]*(i*2-1);
    cout<<ans<<endl;
}