第十七届黑龙江省大学生程序设计竞赛 E.Exclusive Multiplication 个人题解(简单莫比乌斯反演)

E-Exclusive Multiplication_“统信杯” 第十七届黑龙江省大学生程序设计竞赛（正式赛） (nowcoder.com)

题意：设一个整数n,,定义,

现在给你一个长度为n的序列b,问

知识点：莫比乌斯反演

思路：

首先，我们先想办法把俩下标都改成从1开始到n,

现在我们的问题是求(1),(2)

然后，我们开始看f函数，容易发现

所以,.

,

接下来是套路化的东西，我们定义,为i的个数

枚举d

莫反，枚举T

设Q=dT，枚举Q

定义，

我们可以暴力预处理，整体复杂度是(d(i)表示i的约数个数)，在m=2e5时为16782730，肯定是够的，所以就出来了，关于f(i)，我们直接O(n)预处理就可以了，具体可以看代码

代码

#include 
using namespace std;
typedef long long ll;
const ll N = 2e5+5;
const ll mod =1e9+7;
ll p[N],cnt,f[N],u[N],g[N];
bool v[N],low[N];//low(i)表示i的最小质数的个数
void init(){
    u[1]=1;f[1]=1;
    for(ll i=2;i>n;
    for(int i=1;i<=n;++i){
        cin>>b;
        has[b]++;//定义
        maxx=max(maxx,b);
    }
    ll ans=0;
    for(ll i=1;i<=maxx;++i){
        for(ll j=i;j<=maxx;j+=i){//i是j的因子
            ll res=0;
            for(ll w=1;w<=(maxx/j);++w)res=(res+f[i*w]*has[j*w]%mod)%mod;//式子
            res=res*res%mod;
            g[j]=(g[j]+u[i]*res%mod+mod)%mod;//式子
        }
        ans=(ans+g[i])%mod;//累加
    }
    ll inv2=(mod+1)/2;//记得是模意义下
    ans=(ans-n+mod)%mod*inv2%mod;
    cout<>_;
    while(_--){
        solve();
    }
    return 0;
}