P1447 [NOI2010] 能量采集

ziyistudy / 2024-08-06 / 原文

题目传送

容斥思想的一道好题。

题目容易转化为：

\[2\times \sum_{i=1}^n \sum_{j=1}^n (\gcd(i, j))\ - nm. \]

直接求和不好求，不妨转换为枚举 $d=\gcd(i,j)$。

那么 $i,j$ 应该均为 $d$ 的倍数。记 $f(i)=\left \lfloor \frac{n}{i} \right \rfloor \cdot \left \lfloor \frac{m}{i} \right \rfloor$，但发现会有虽然都是 $i$ 的倍数，但 $\gcd$ 并不是 $i$ 的数，考虑如何去除。

记 $g(i)$ 为 $\gcd(x,y)=i$ 的数量，容易发现 $f(i)={\textstyle \sum \limits_{j=1}^{\left \lfloor \frac{n}{i} \right \rfloor} g(i\cdot j)}$。

$f(i)$ 是好求的，我们倒着处理 $g(i)$。复杂度是调和级数 $\mathcal O(n\log n)$。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=1e9+7;
// head
const int N=1e5+5;
int f[N],g[N];
signed main() 
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

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