2020 Multi-University Training Contest 1---- HDU--6760、Math is Simple（数论、莫比乌斯反演）

题目链接

题面：

题意：
求：
f(n)=1≤a<b≤n,gcd(a,b)=1,a+b>=n∑​ab1​

题解：
以下均基于 $n\ge 2$n≥2
（1）

f(n)=1≤a<b≤n,gcd(a,b)=1,a+b>=n∑​ab1​
 
 
f(n−1)=1≤a<b≤n−1,gcd(a,b)=1,a+b>=n−1∑​ab1​
 
 
（2） 考虑 $f\left(n\right)$f(n)和 $f(n-1)$f(n−1)相差了啥。
 

f(n)=f(n−1)+1≤a<n,gcd(a,n)=1∑​an1​−1≤a<b≤n−1,gcd(a,b)=1,a+b=n−1∑​ab1​

其中
①、 1≤a<n,gcd(a,n)=1∑​an1​ 是 $f\left(n\right)$f(n) 较 $f(n-1)$f(n−1) 多的 $b=n$b=n 的那一些，因为 $n\ge 2$n≥2，所以上式又等于 $\sum _{1\le a\le n,gcd(a,n)=1}\frac{1}{an}$1≤a≤n,gcd(a,n)=1∑​an1​
 

②、 1≤a<b≤n−1,gcd(a,b)=1,a+b=n−1∑​ab1​是 $f\left(n\right)$f(n) 较 $f(n-1)$f(n−1)少的 $a+b==n-1$a+b==n−1那一些
 

(3)
我们设 g(n)=1≤a<b≤n,gcd(a,b)=1,a+b=n∑​ab1​
 
那么
g(n)=1≤a<b≤n,gcd(a,b)=1,a+b=n∑​ab1​=n1​1≤a<b≤n,gcd(a,b)=1,a+b=n∑​(a1​+b1​)

由更相减损 $gcd(a,b)=gcd(a-b,b)=gcd(a,b-a)$gcd(a,b)=gcd(a−b,b)=gcd(a,b−a) 得到 $gcd(a,b)=gcd(a,n)=gcd(b,n)=1$gcd(a,b)=gcd(a,n)=gcd(b,n)=1

那么
$g\left(n\right)=\frac{1}{n}\sum _{1\le a\le n,gcd(a,n)=1}\frac{1}{a}$g(n)=n1​1≤a≤n,gcd(a,n)=1∑​a1​
 
但是 $g\left(2\right)=0,n=2$g(2)=0,n=2时比较特殊，也就是说，n=2时并不符合上式，但是我们下文中的 $g\left(2\right)=0$g(2)=0符合要求。

（4） 我们发现了啥。

f(n)=1≤a<b≤n,gcd(a,b)=1,a+b>=n∑​ab1​
 

g(n)=1≤a<b≤n,gcd(a,b)=1,a+b=n∑​ab1​

$f\left(n\right)=f(n-1)+g\left(n\right)-g(n-1)=f(n-2)+g(n-1)-g(n-2)+g\left(n\right)-g(n-1)=f(n-2)+g\left(n\right)-g(n-2)=f(n-3)+g\left(n\right)-g(n-3)=...=f\left(2\right)-g\left(2\right)+g\left(n\right)$f(n)=f(n−1)+g(n)−g(n−1)=f(n−2)+g(n−1)−g(n−2)+g(n)−g(n−1)=f(n−2)+g(n)−g(n−2)=f(n−3)+g(n)−g(n−3)=...=f(2)−g(2)+g(n)

$f\left(2\right)=\frac{1}{2},g\left(2\right)=0$f(2)=21​,g(2)=0

$f\left(n\right)=\frac{1}{2}+g\left(n\right)$f(n)=21​+g(n)
 

（5） 转化为求 $g\left(n\right)$g(n)

$g\left(n\right)=\frac{1}{n}\sum _{1\le a\le n,gcd(a,n)=1}\frac{1}{a}$g(n)=n1​1≤a≤n,gcd(a,n)=1∑​a1​

注意到， $g\left(2\right)$g(2)不满足上式，又 $n\ge 2$n≥2，所以其余的 n 均满足上式。

对于任意的正整数 $n,{\sum }_{d\mid n}\mu \left(d\right)=[n=1]-->n=1时{\sum }_{d\mid n}\mu \left(d\right)=1，n\ne 1时{\sum }_{d\mid n}\mu \left(d\right)=0$n,∑d∣n​μ(d)=[n=1]−−>n=1时∑d∣n​μ(d)=1，n​=1时∑d∣n​μ(d)=0。

$g\left(n\right)=\frac{1}{n}{\sum }_{i=1}^n\frac{1}{i}\sum _{d\mid gcd(i,n)}\mu \left(d\right)$g(n)=n1​i=1∑n​i1​d∣gcd(i,n)∑​μ(d)

转换一下枚举顺序，先枚举 $d\mid gcd(i,n)$d∣gcd(i,n)得

$g\left(n\right)=\frac{1}{n}\sum _{d\mid gcd(i,n)}\mu \left(d\right){\sum }_{i=1}^n\frac{1}{i}$g(n)=n1​d∣gcd(i,n)∑​μ(d)i=1∑n​i1​

$g\left(n\right)=\frac{1}{n}\sum _{d\mid n}\mu \left(d\right){\sum }_{i=1}^n\left[d\mid i\right]\frac{1}{i}$g(n)=n1​d∣n∑​μ(d)i=1∑n​[d∣i]i1​
其中 $\left[d\mid i\right]$[d∣i] 表示 d 能整除 i 时为1，否则为0。
$1--n中有\lfloor {\displaystyle \frac{n}{d}}\rfloor 个i可以被d整除$1−−n中有⌊dn​⌋个i可以被d整除

$g\left(n\right)=\frac{1}{n}\sum _{d\mid n}\mu \left(d\right){\sum }_{i=1}^{\lfloor {\displaystyle \frac{n}{d}}\rfloor }\frac{1}{i\ast d}$g(n)=n1​d∣n∑​μ(d)i=1∑⌊dn​⌋​i∗d1​

我们设 $s\left(n\right)={\sum }_{i=1}^n\frac{1}{i}$s(n)=i=1∑n​i1​

那么有 $g\left(n\right)=\frac{1}{n}\sum _{d\mid n}\frac{\mu \left(d\right)}{d}\ast s(\lfloor {\displaystyle \frac{n}{d}}\rfloor )$g(n)=n1​d∣n∑​dμ(d)​∗s(⌊dn​⌋)

(6)莫比乌斯函数 $\mu$μ

当 N 包含相等的质因子时 $\mu \left(N\right)=0$μ(N)=0，当 N 所包含的质因子各不相同时，若 N 有偶数个质因子 $\mu \left(N\right)=1$μ(N)=1，若 N 有奇数个质因子 $\mu \left(N\right)=-1$μ(N)=−1

（7）总结题解：
我们需要开一个长度为1e8的数组，维护前缀和 s。int 大约需要380M。
对于每一个n，我们首先要注意到，如果 n=2，那么无法套用公式求解，最终答案为 1/2。
如果 n!=2，那么我们对n进行唯一分解，枚举 n 的质因子的组合即可。其中每个质因子在每个因子中最多只出现一次即可，因为当 N 包含相等的质因子时 $\mu =0$μ=0
时间复杂度 $O(n+t\ast \sqrt{n})$O(n+t∗n ​)

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100000001;
const int maxm=100100;
const int up=100000;

int inv[maxn],fac[40];
int cnt=0,ans=0,n;

void only(int x)
{
    cnt=0;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i!=0) continue;
        fac[++cnt]=i;
        while(x%i==0) x/=i;
    }
    if(x>1) fac[++cnt]=x;
}

void dfs(int now,int d,int mu)
{
    if(now==cnt+1)
    {
        ans=(ans+1ll*mu*(inv[d]-inv[d-1])*inv[n/d]%mod+mod)%mod;
        return ;
    }
    dfs(now+1,d,mu);
    dfs(now+1,d*fac[now],mu*(-1));
}

int main(void)
{
    inv[1]=1;
    for(int i=2;i<maxn;i++)
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=2;i<maxn;i++)
        inv[i]=(inv[i-1]+inv[i])%mod;

    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d",&n);
        if(n==2)
        {
            printf("%d\n",(inv[2]-inv[1]+mod)%mod);
            continue;
        }
        only(n);
        ans=0;
        dfs(1,1,1);
        ans=1ll*ans*(inv[n]-inv[n-1]+mod)%mod;
        ans=((ans+inv[2]-inv[1])%mod+mod)%mod;
        printf("%d\n",ans);
    }
    return 0;
}