牛客挑战赛46 E.反演

设

考虑先枚举得：

考虑先枚举：

由于莫比乌斯函数的性质，我们只需要枚举所有莫比乌斯函数非零的因子d（即质因子最高幂次为1）。

函数的答案可以分块计算。

而所有倍数的因子个数和可以在dfs的过程中计算出来。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
#define wzh(x) cerr<<#x<<'='<<x<<endl;
LL n;
int m;
const int mod=998244353;
LL cal(LL x){
  LL y=0;
  for(LL i=1,j;i<=x;i=j+1){
    j=min(x,x/(x/i));
    y+=(j-i+1)%mod*(x/i)%mod;
    y%=mod;
  }
  return y;
}
vector<pair<int,int>>pr;
LL ans;
void dfs(int now,int mu,LL val,LL d,LL oh){
  if(now==pr.size()){
    ans+=mu*cal(n/d)%mod*val%mod*oh%mod;
    ans%=mod;
    return;
  }
    //不选这个数
  dfs(now+1,mu,val,d,oh*((pr[now].second+2)*(pr[now].se+1)/2)%mod);
  if(d*pr[now].fi<=n){//选这个数
    dfs(now+1,-mu,val*((pr[now].second+1)*(pr[now].se)/2)%mod,d*pr[now].fi,oh);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin>>n>>m;
  auto is_pr =[&](int x){
    for(int i=2;i<x;i++){
      if(x%i==0)return 0;
    }
    return 1;
  };
  for(int i=2;i<=m;i++){
    if(is_pr(i)){
      int z=m,q=0;
      while(z){
        q+=z/i;
        z/=i;
      }
      pr.pb({i,q});
    }
  }
  dfs(0,1,1,1,1);
  cout<<ans<<'\n';
  return 0;
}