HDU - 5528 Count a * b （欧拉函数、除数函数）

题目vj链接

题面：

题意：
求解：
$g\left(m\right)=\sum _{m\mid n}f\left(m\right)，f\left(m\right)={\sum }_{a=0}^{m-1}{\sum }_{b=0}^{m-1}[a\ast b\%m\ne 0]$g(m)=m∣n∑​f(m)，f(m)=a=0∑m−1​b=0∑m−1​[a∗b%m​=0]。

题解：
①先化简 $f\left(m\right)$f(m)：
$f\left(m\right)={\sum }_{a=0}^{m-1}{\sum }_{b=0}^{m-1}[a\ast b\%m\ne 0]$f(m)=a=0∑m−1​b=0∑m−1​[a∗b%m​=0]

$f\left(m\right)=m^2-{\sum }_{a=0}^{m-1}{\sum }_{b=0}^{m-1}[a\ast b\%m=0]$f(m)=m2−a=0∑m−1​b=0∑m−1​[a∗b%m=0]

$f\left(m\right)=m^2-{\sum }_{a=1}^m{\sum }_{b=1}^m[a\ast b\%m=0]$f(m)=m2−a=1∑m​b=1∑m​[a∗b%m=0]（a=0与a=m的贡献一致，b=0与b=m的贡献一致）

设 $p\left(m\right)={\sum }_{a=1}^m{\sum }_{b=1}^m[a\ast b\%m=0]$p(m)=a=1∑m​b=1∑m​[a∗b%m=0]

②求解 $p\left(m\right)$p(m)：

$p\left(m\right)={\sum }_{a=1}^m{\sum }_{b=1}^m[a\ast b\%m=0]$p(m)=a=1∑m​b=1∑m​[a∗b%m=0]

$={\sum }_{a=1}^m{\sum }_{b=1}^{m}m\mid (a\ast b)$=a=1∑m​b=1∑m​m∣(a∗b)

$={\sum }_{a=1}^m{\sum }_{b=1}^m\frac{m}{gcd(m,a)}\mid (\frac{a}{gcd(m,a)}\ast b)$=a=1∑m​b=1∑m​gcd(m,a)m​∣(gcd(m,a)a​∗b)

$={\sum }_{a=1}^m{\sum }_{b=1}^m\frac{m}{gcd(m,a)}\mid b$=a=1∑m​b=1∑m​gcd(m,a)m​∣b ，因为 $gcd(\frac{m}{gcd(m,a)},\frac{a}{gcd(m,a)})=1$gcd(gcd(m,a)m​,gcd(m,a)a​)=1

$={\sum }_{a=1}^m\frac{m}{\frac{m}{gcd(a,m)}}$=a=1∑m​gcd(a,m)m​m​

$={\sum }_{a=1}^{m}gcd(a,m)$=a=1∑m​gcd(a,m)

$={\sum }_{d=1}^m{\sum }_{a=1}^m\left[gcd\right(a,m)=d]\ast d$=d=1∑m​a=1∑m​[gcd(a,m)=d]∗d

$=\sum _{d\mid m}{\sum }_{a=1}^m\left[gcd\right(a,m)=d]\ast d$=d∣m∑​a=1∑m​[gcd(a,m)=d]∗d

$=\sum _{d\mid m}d\ast {\sum }_{a=1}^{\frac{m}{d}}\left[gcd\right(a,\frac{m}{d})=1]$=d∣m∑​d∗a=1∑dm​​[gcd(a,dm​)=1]

$=\sum _{d\mid m}d\ast \phi \left(\frac{m}{d}\right)$=d∣m∑​d∗φ(dm​)

③带入 $g\left(n\right)$g(n):
$g\left(m\right)=\sum _{m\mid n}f\left(m\right)$g(m)=m∣n∑​f(m)

$=\sum _{m\mid n}(m^2-\sum _{d\mid m}d\ast \phi (\frac{m}{d}\left)\right)$=m∣n∑​(m2−d∣m∑​d∗φ(dm​))

我们令 $a\left(n\right)=\sum _{m\mid n}{m}^2,b\left(n\right)=\sum _{m\mid n}\sum _{d\mid m}d\ast \phi \left(\frac{m}{d}\right),g\left(n\right)=a\left(n\right)-b\left(n\right)$a(n)=m∣n∑​m2, b(n)=m∣n∑​d∣m∑​d∗φ(dm​), g(n)=a(n)−b(n)

④求解 $a\left(n\right)$a(n):

我们知道除数函数 $\sigma (k,x)=\sum _{d\mid x}{d}^k$σ(k,x)=d∣x∑​dk是积性函数，即若 $gcd(x,y)==1$gcd(x,y)==1，则 $\sigma (k,x\ast y)=\sigma (k,x)\ast \sigma (k,y)$σ(k,x∗y)=σ(k,x)∗σ(k,y)

我们设 $\sigma (2,n)=\sum _{d\mid n}{d}^2$σ(2,n)=d∣n∑​d2

将n唯一分解 $n=p_1^{e_1}\ast p_2^{e_2}\ast ...\ast p_k^{e_k}$n=p1e1​​∗p2e2​​∗...∗pkek​​
其中 $(p_1^{e_1},p_2^{e_2},...,p_k^{e_k})$(p1e1​​,p2e2​​,...,pkek​​) 两两互质

$\sigma (2,n)=\sigma (2,p_1^{e_1})\ast \sigma (2,p_2^{e_2})\ast ...\ast \sigma (2,p_k^{e_k})$σ(2,n)=σ(2,p1e1​​)∗σ(2,p2e2​​)∗...∗σ(2,pkek​​)

对于 $\sigma (2,p_i^{e_i})=(p_i^0{)}^2+(p_i^1{)}^2+...+(p_i^{e_i}{)}^2$σ(2,piei​​)=(pi0​)2+(pi1​)2+...+(piei​​)2

我们可以看作 $a_1=1,q=p_i^2$a1​=1,q=pi2​ 的等比数列求和。这样 $O\left(1\right)$O(1)即可求解。
因为这题要求对 $2^{64}$264 取模，逆元不好处理，直接暴力计算即可。（因为 $e_i$ei​不会很大）

⑤求解 $b\left(n\right)$b(n):
$b\left(n\right)=\sum _{m\mid n}\sum _{d\mid m}d\ast \phi \left(\frac{m}{d}\right)$b(n)=m∣n∑​d∣m∑​d∗φ(dm​)

先枚举 $d$d

$b\left(n\right)=\sum _{d\mid n}d\ast \sum _{d\mid m,m\mid n}\phi \left(\frac{m}{d}\right)$b(n)=d∣n∑​d∗d∣m,m∣n∑​φ(dm​)

$=\sum _{d\mid n}d\ast \sum _{(k\ast d)\mid n}\phi \left(k\right)$=d∣n∑​d∗(k∗d)∣n∑​φ(k)

$=\sum _{d\mid n}d\ast \sum _{k\mid \frac{n}{d}}\phi \left(k\right)$=d∣n∑​d∗k∣dn​∑​φ(k)

$n$n 的因子的欧拉函数之和为 $n$n

$b\left(n\right)=\sum _{d\mid n}d\ast \frac{n}{d}=\sum _{d\mid n}n=n\ast \sigma (0,n)=n\ast \prod (e_i+1)$b(n)=d∣n∑​d∗dn​=d∣n∑​n=n∗σ(0,n)=n∗∏(ei​+1)

⑥综上：
$g\left(n\right)=\sigma (2,n)-n\ast \prod (e_i+1)$g(n)=σ(2,n)−n∗∏(ei​+1)

时间复杂度 $O(T\ast \sqrt{n})$O(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)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

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

int prime[maxn],cnt=0;
bool ha[maxn];
int p[55],e[55],tot=0;

void Prime(void)
{
    ha[1]=true;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i])
            prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<maxn;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

void only(int n)
{
    memset(e,0,sizeof(e));
    tot=0;
    for(int i=1;prime[i]*prime[i]<=n;i++)
    {
        if(n%prime[i]) continue;
        p[++tot]=prime[i];
        while(n%prime[i]==0)
            e[tot]++,n/=prime[i];
    }
    if(n>1) p[++tot]=n,e[tot]=1;
}

int main(void)
{
    Prime();
    int tt,n;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d",&n);
        only(n);
        llu a=1,b=n;
        for(int i=1;i<=tot;i++)
        {
            b*=(e[i]+1);
            llu ans=1,pk=1;
            for(int j=1;j<=e[i];j++)
                pk=pk*p[i],ans=ans+pk*pk;
            a*=ans;
        }
        printf("%llu\n",a-b);
    }
    return 0;
}