Problem H. Curious（莫反）

admin管理员组

文章数量:1612099

题意：请问在a数组里满足的对数的个数也就是求然后对于每一个询问x都输出一个值代表对数的个数

思路：莫比乌斯反演。既然确定了是莫反，那么就要开始给函数赋予意义了，辣么首先另我们需要求的结果为

然后我们就可以求

到这一步之后我们来仔细看看这个式子

首先这个式子要求的是gcd为x的倍数的对子

也就是说此时的里都包含因子d，又因为d可以整除x所以可以整除x，也就是说我们这个F(x)所存储的值为在整个a数组中存在可以整除x的对数的个数

然后通过反演我们可以得到这样的一个式子:这个式子就是直接通过反演得来的

在莫反中，的值是可以求出来的，那么接下来我们只需要搞定F(d)的值即可，由上面的推导可以知道，F(d)的含义就是gcd为d的倍数的对子的个数.对于这个值我们发现如果的gcd值是d的倍数当且仅当都是d的倍数

所以我们只需要预处理出的个数即可，我们记这个数量为h(d)所以

所以最终这个式子就可以变成这个美丽的样子：

写到了这一步如果是一般的问题就已经解决了，但是在这里我们还需要一步来优化时间复杂度，因为在这里我们如果直接暴力遍历每一个x和d那么时间复杂度为显然是会超时的

那么如何优化呢，这是我的思路：

首先，为什么之前需要遍历x和d因为在我们这个式子里它不仅仅有x也有(d/x)这种形式，所以我们迫不得已必须遍历两个变量且都是1e5级别的，所以我们需要思考怎么让它的变量减少最好两个变量统一，那么我们开始思考如过前面的x变成（d/x）的话，我们的x｜d需要变成什么？

我们遍历每一个x的倍数，因为i*x必定可以整除i的因子，然后存在h数组里，表示在这些a数组中有多少个可以整除j的数字的个数。

最终的式子就变成了：

len为最大的倍数

所以最终我们的伪代码就是

for i:1-->m
  ll X=i*x;
  记录下最大的能存在的倍数len
  for j:遍历每一个i的因子
    h[j]+=a[X]的数量
for i:1-->len
  ans+=h[i]*h[i]*mu[i];
  h[i]=0;//记得请空h数组，因为每一次都是不一样的

最后上代码：

#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <queue>
#include <iostream>
#include <cmath>
#include <cstring>
#include <set>
#include <iomanip>
#include <stdexcept>
#include <fstream>
#define ll long long
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e5+7;
const double pi=acos(-1);
int prime[N];
bool vis[N];
int mu[N];
ll n,m,k;
ll ans[N],num[N],h[N];
void init(){
    mu[1]=1;
    int cnt=0;
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=N;i++)
    {
        if(!vis[i]){
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                break;
            }
            else mu[prime[j]*i]=-mu[i];
        }
    }
}
vector<int>v[N];
void getyinshu(){
    for(int i=1;i<N;++i){
        for(int j=1;j*j<=i;++j){
            if(i%j==0){
                v[i].push_back(j);
                if(j*j!=i) v[i].push_back(i/j);//存下所有i的因子
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    init();
    getyinshu();
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m>>k;
        for(int i=1;i<N;++i){
            num[i]=0;
            ans[i]=-1;
        }
        vector<int>a(n+1);
        for(int i=1;i<=n;++i){
            cin>>a[i];
            num[a[i]]++;//统计每个数的数量
        }
        ll len;
        while(k--){
            int x;
            cin>>x;
            if(ans[x]!=-1){
                cout<<ans[x]<<endl;
                continue;
            }
            for(int i=1;i<=m;++i){
                ll X=i*x;//从1开始遍历每一个倍数的X值
                if(X>m) break;
                len=i;
                for(auto j:v[i]){
                    h[j]+=num[X];//因为一个数X的值为i*x时它就可以整除所有的i的因子，所以遍历i所有的因子
                    //h数组存下所有包含j因子的数的数量
                }
            }
            ll res=0;
            for(ll i=1;i<=len;++i){//len存的是最大的倍数
                res+=h[i]*h[i]*mu[i];
                h[i]=0;
            }
            ans[x]=res;//记忆化，避免重复遍历
            cout<<ans[x]<<endl;
        }
    }
    return 0;
}

本文标签： Problemcurious