数论推式子题选讲

· · 算法·理论

A Luogu P1891

题目

求

\sum_{i = 1}^{n}{\operatorname{lcm}(i,n)} ### Solution 直接推式子 $$ \begin{align*} &\sum_{i = 1}^{n}{\operatorname{lcm}(i,n)} \\ &= \sum_{i = 1}^{n}{in \gcd(i,n)^{-1}} \\ &= n \sum_{d | n}{d^{-1} \sum_{i = 1}^{n}{i [\gcd(i,n) = d]}} \\ &= n \sum_{d | n}{d^{-1} \sum_{i = 1}^{\frac{n}{d}}{id [gcd(i,\frac{n}{d}) = 1]}} \\ &= n \sum_{d | n}{\sum_{i = 1}^{\frac{n}{d}}{i [\gcd(i,\frac{n}{d}) = 1]}} \end{align*} $$ 此时我们发现只有第二个和式比较难处理，我们把它拿出来单独处理。 设 $f(x) = \sum_{i = 1}^{x}{i [\gcd(i,x) = 1]}$，我们只要求出 $f$，就能做出来了。这个式子是小于等于 $x$ 中所有与 $x$ 互质的数的和，首先，小于等于 $x$ 且与它互质的数量是好求的，是 $\varphi(x)$，根据欧几里得算法，$\gcd(x,i) = \gcd(x,x - i)$，那么如果一个数 $i$ 和 $x$ 互质，那么 $x - i$ 也与 $x$ 互质，于是我们把算进答案里的这些数反过来再写一遍，那么就成了 $\varphi(x)$ 个 $x$ 的和，再除以 $2$ 就行了。 于是，我们得到了 $f$ 的表达式，$f(x) = \frac{\varphi(x) x}{2}$，带入原式 $$ Ans = n \sum_{d | n}{\frac{\varphi(\frac{n}{d}) \frac{n}{d}}{2}} \\ = n \sum_{d | n}{\frac{\varphi(d) d}{2}} $$ 欧拉筛预处理欧拉函数枚举因数计算答案即可。 时间复杂度 $O(n + T \sqrt{n})$。 ### AC Code ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long #define uni unsigned int #define ull unsigned long long #define lll __int128 #define ld long double #define pb push_back #define mk make_pair #define ppcnt __builtin_popcount #define sort stable_sort ll read() { ll k=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } void write(char c){putchar(c);} int St[100],Top; void write(int x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } void write(ll x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } int prime[1000010],cnt=0,phi[1000010]; void init() { phi[1]=1; for(int i=2;i<=1000000;++i) { if(!phi[i]) { phi[i]=i-1; prime[++cnt]=i; } for(int j=1;j<=cnt&&i*prime[j]<=1000000;++j) { phi[i*prime[j]]=phi[i]*phi[prime[j]]; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } } } } void solve() { int n=read(); ll ans=0; for(int i=1;i*i<=n;++i) { if(n%i==0) { ans+=(1ll*phi[i]*i+1)>>1; if(i*i!=n)ans+=(1ll*phi[n/i]*(n/i)+1)>>1; } } ans*=n; write(ans),write('\n'); } int main() { std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); init(); int T=read(); while(T--)solve(); return 0; } ``` ## [B Luogu P2257](https://www.luogu.com.cn/problem/P2257) ### 题目 求 $$ \sum_{i = 1}^{n}{\sum_{j = 1}^{m}{[\gcd(i,j) \text{是质数}]}} $$ $T \le 10^4 , n , m \le 10^7$。 ### Solution 推式子，令 $n le m$，下面会用 $\in prime$ 表示这个数是质数，用 $p$ 代表只枚举满足条件的质数 $$ \begin{align*} &\sum_{i = 1}^{n}{\sum_{j = 1}^{m}{[\gcd(i,j) \in prime]}} \\ &= \sum_{p}^{n}{\sum_{i = 1}^{n}{\sum_{j = 1}^{m}{[\gcd(i,j) = p]}}} \\ &= \sum_{p}^{n}{\sum_{i = 1}^{\lfloor \frac{n}{p} \rfloor}{\sum_{j = 1}^{\lfloor \frac{m}{p} \rfloor}{[\gcd(i,j) = 1]}}} \\ &= \sum_{p}^{n}{\sum_{i = 1}^{\lfloor \frac{n}{p} \rfloor}{\sum_{j = 1}^{\lfloor \frac{m}{p} \rfloor}{\sum_{k | i , k | j}{\mu(k)}}}} \\ &= \sum_{p}^{n}{\sum_{k = 1}^{\lfloor \frac{n}{p} \rfloor}{\mu(k) \lfloor \frac{n}{pk} \rfloor \lfloor \frac{m}{pk} \rfloor}} \end{align*} $$ 此时考虑令 $t = pk$，枚举 $t \begin{align*} &Ans = \sum_{t = 1}^{n}{\lfloor \frac{n}{t} \rfloor \lfloor \frac{m}{t} \rfloor \sum_{p | t}{\mu(\frac{t}{p})}} \end{align*}

此时后面的和式已经和前面无关了，可以预处理，前面的是一个下取整式，于是直接二维整除分块即可。
时间复杂度 O(n \log \log n + T \sqrt{n})。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uni unsigned int
#define ull unsigned long long
#define lll __int128
#define ld long double
#define pb push_back
#define mk make_pair
#define ppcnt __builtin_popcount
#define sort stable_sort
ll read()
{
    ll k=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void write(char c){putchar(c);}
int St[100],Top;
void write(int x)
{
    if(x==0){putchar('0');return;}
    if(x<0)putchar('-'),x=-x;
    Top=0;while(x)St[++Top]=x%10,x/=10;
    while(Top)putchar((char)('0'+St[Top--]));
}
void write(ll x)
{
    if(x==0){putchar('0');return;}
    if(x<0)putchar('-'),x=-x;
    Top=0;while(x)St[++Top]=x%10,x/=10;
    while(Top)putchar((char)('0'+St[Top--]));
}
int prime[5000010],cnt=0;
ll mu[10000010],f[10000010];
bitset<10000010> vis;
void init()
{
    mu[1]=1;
    for(int i=2;i<=10000000;++i)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=10000000;++j)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=cnt;++i)for(int j=prime[i];j<=10000000;j+=prime[i])f[j]+=mu[j/prime[i]];
    for(int i=1;i<=10000000;++i)f[i]+=f[i-1];
}
void solve()
{
    ll n=read(),m=read(),ans=0;
    if(n>m)swap(n,m);
    for(ll l=1,r;l<=n;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        ans+=(f[r]-f[l-1])*(n/l)*(m/l);
    }
    write(ans),write('\n');
}
int main()
{
    std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    init();
    int T=read();
    while(T--)solve();
    return 0;
}

C Luogu P2260

题目

求

\sum_{i = 1}^{n}{\sum_{j = 1}^{m}{(n \bmod i) \times (m \bmod j) , i \neq j}} ### Solution 推式子，令 $n \le m \begin{align*} &\sum_{i = 1}^{n}{\sum_{j = 1}^{m}{(n \bmod i) \cdot (m \bmod j) , i \neq j}} \\ &= \sum_{i = 1}^{n}{\sum_{j = 1}^{m}{(n \bmod i) \cdot (m \bmod j)}} - \sum_{i = 1}^{n}{(n \bmod i) \cdot (m \bmod i)} \end{align*}

先算前一部分

\begin{align*} &\sum_{i = 1}^{n}{\sum_{j = 1}^{m}{(n \bmod i) \cdot (m \bmod j)}} \\ &= (\sum_{i = 1}^{n}{n \bmod i})(\sum_{i = 1}^{m}{m \bmod i})\\ \end{align*}

设 f(x) = \sum_{i = 1}^{x}{x \bmod i}，考虑求 f 的表达式

\begin{align*} &\sum_{i = 1}^{x}{x \bmod i} \\ &= \sum_{i = 1}^{x}{x - i \lfloor \frac{x}{i} \rfloor} \\ &= x^2 - \sum_{i = 1}^{x}{\lfloor \frac{x}{i} \rfloor} \end{align*}

后面的和式直接数论分块就能算，于是前面的式子就处理完了，再处理后面的

\begin{align*} &\sum_{i = 1}^{n}{(n \bmod i) \cdot (m \bmod i)} \\ &= \sum_{i = 1}^{n}{(n - i \lfloor \frac{n}{i} \rfloor) \cdot (m - i \lfloor \frac{m}{i} \rfloor)} \\ &= \sum_{i = 1}^{n}{nm - ni \lfloor \frac{m}{i} \rfloor - mi \lfloor \frac{n}{i} \rfloor + i^2 \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor} \\ &= n^2 m - n \sum_{i = 1}^{n}{i \lfloor \frac{m}{i} \rfloor} - m \sum_{i = 1}^{n}{i \lfloor \frac{n}{i} \rfloor} + \sum_{i = 1}^{n}{i^2 \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor} \end{align*}

对每个和式分别写一个数论分块即可。
时间复杂度 O(\sqrt{n} + \sqrt{m})。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define uni unsigned int
#define ull unsigned long long
#define lll __int128
#define ld long double
#define pb push_back
#define mk make_pair
#define ppcnt __builtin_popcount
#define sort stable_sort
const ll mod=19940417;
ll read()
{
    ll k=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void write(char c){putchar(c);}
int St[100],Top;
void write(int x)
{
    if(x==0){putchar('0');return;}
    if(x<0)putchar('-'),x=-x;
    Top=0;while(x)St[++Top]=x%10,x/=10;
    while(Top)putchar((char)('0'+St[Top--]));
}
void write(ll x)
{
    if(x==0){putchar('0');return;}
    if(x<0)putchar('-'),x=-x;
    Top=0;while(x)St[++Top]=x%10,x/=10;
    while(Top)putchar((char)('0'+St[Top--]));
}
int main()
{
    std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n=read(),m=read();
    if(n>m)swap(n,m);
    ll Ans=n*n%mod*m%mod*m%mod-n*n%mod*m%mod;
    Ans%=mod;
    ll ansn1=0,ansm1=0;
    for(ll l=1,r;l<=n;l=r+1)
    {
        r=(n/(n/l));
        (ansn1+=(r*(r+1)/2-l*(l-1)/2)%mod*(n/l)%mod)%=mod;
    }
    for(ll l=1,r;l<=m;l=r+1)
    {
        r=(m/(m/l));
        (ansm1+=(r*(r+1)/2-l*(l-1)/2)%mod*(m/l)%mod)%=mod;
    }
    (Ans+=ansn1*ansm1%mod)%=mod;
    (Ans-=n*n%mod*ansm1%mod)%=mod;
    (Ans-=(m*m%mod-m)*ansn1%mod)%=mod;
    ansm1=0;
    for(ll l=1,r;l<=n;l=r+1)
    {
        r=min(n,(m/(m/l)));
        (ansm1+=(r*(r+1)/2-l*(l-1)/2)%mod*(m/l)%mod)%=mod;
    }
    (Ans+=n*ansm1%mod)%=mod;
    ll ans=0;
    for(ll l=1,r;l<=n;l=r+1)
    {
        r=min({n,n/(n/l),m/(m/l)});
        ll sum=((lll)r*(r+1)*(2*r+1)/6%mod)-((lll)(l-1)*(l)*(2*l-1)/6%mod);
        ans+=(n/l)*(m/l)%mod*sum%mod;
    }
    (Ans-=ans)%=mod;
    write((Ans+mod)%mod);
    return 0;
}

D Luogu P2303

题目

求

\sum_{i = 1}^{n}{\gcd(i,n)} ### Solution 推式子基本功 $$ \begin{align*} &\sum_{i = 1}^{n}{\gcd(i,n)} \\ &= \sum_{d | n}{d \sum_{i = 1}^{n}{[\gcd(i,n) = d]}} \\ &= \sum_{d | n}{d \sum_{i = 1}^{\frac{n}{d}}{[\gcd(i,\frac{n}{d}) = 1]}} \\ &= \sum_{d | n}{d \varphi(\frac{n}{d})} \\ &= \sum_{d | n}{\frac{n}{d} \varphi(d)} \\ &= \sum_{d | n}{\frac{n}{d} d \prod_{p | d}{\frac{p - 1}{p}}} \\ &= n \sum_{d | n}{\prod_{p | d}{\frac{p - 1}{p}}} \end{align*} $$ 考虑对这个式子因式分解，写成一堆乘积的形式，于是我们发现，对某个质数 $p$，把它提出来后，除了它以外的东西应该是一样的，它的贡献应该是若干个选他的贡献和一个不选它的贡献，选的贡献应该是若干个 $\frac{p - 1}{p}$ 的和，不选的应该是 $1$。那么它贡献的次数是多少呢，考虑 $n$ 的质因数分解，$p$ 的贡献次数应该是 $n_p$，那么它的总贡献应该是 $n_p \frac{p - 1}{p} + 1$。 带回原式，得到 $$ \begin{align*} &Ans = \prod_{p | n}{n_p \frac{p - 1}{p} + 1} \\ &=\prod_{p | n}{\frac{n_p (p - 1) + p}{p}} \\ &=\prod_{p | n}{\frac{n_p p - n_p + p}{p}} \end{align*} $$ 时间复杂度 $O(\sqrt{n})$。 ### AC Code ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long #define uni unsigned int #define ull unsigned long long #define lll __int128 #define ld long double #define pb push_back #define mk make_pair #define ppcnt __builtin_popcount #define sort stable_sort ll read() { ll k=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } void write(char c){putchar(c);} int St[100],Top; void write(int x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } void write(ll x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } int main() { std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); ll n=read(); ll ans=n; for(ll i=2;i*i<=n;++i) { if(n%i==0) { ll cnt=0; while(n%i==0)n/=i,cnt++; ans/=i; ans*=cnt*i-cnt+i; } } if(n>1) { ans/=n; ans*=n*2-1; } write(ans); return 0; } ``` ## [E Luogu P3312](https://www.luogu.com.cn/problem/P3312) ### 题目 有一张 $n \times m$ 的数表，其第 $i$ 行第 $j$ 列($1\le i\le n$，$1\le j\le m$)的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$，计算数表中不大于 $a$ 的数之和。 $n , m \le 10^5 , q \le 2 \times 10^4$。 ### Solution 首先，我们能发现，每个格子里的数字应该是 $\gcd(i,j)$ 的因数和函数的值 $\sigma(\gcd(i,j))$。 然后，我们不管 $a$ 的限制，令 $n \le m$，开始推式子 $$ \begin{align*} &\sum_{i = 1}^{n}{\sum_{j = 1}^{m}{\sigma(\gcd(i,j))}} \\ &= \sum_{d = 1}^{n}{\sigma(d) \sum_{i = 1}^{n}{\sum_{j = 1}^{m}{[\gcd(i,j) = d]}}} \\ &= \sum_{d = 1}^{n}{\sigma(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}{\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}{[\gcd(i,j) = 1]}}} \\ &= \sum_{d = 1}^{n}{\sigma(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}{\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}{\sum_{k | i , k | j}{\mu(k)}}}} \\ &= \sum_{d = 1}^{n}{\sigma(d) \sum_{k = 1}^{\lfloor \frac{n}{d} \rfloor}{\mu(k) \lfloor \frac{n}{dk} \rfloor \lfloor \frac{m}{dk} \rfloor}} \\ &= \sum_{t = 1}^{n}{\lfloor \frac{n}{t} \rfloor \lfloor \frac{m}{t} \rfloor \sum_{d | t}{\sigma(d) \mu(\frac{t}{d})}} \end{align*} $$ 这个时候已经可以数论分块做了。 下面来考虑 $a$ 的限制。我们发现后面的这个和式是跟 $\sigma(d)$ 有关的，那么代表着只有在 $\sigma(d)$ 小于等于 $a$ 的时候才会对这个和式产生贡献，那么我们考虑离线所有询问，按 $a$ 排序，用一种数据结构维护单点改和区间和，每次询问前把新增的会产生贡献的数加进来。 时间复杂度 $O(n \ln n + q \sqrt{n})$。 ### AC Code ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long #define uni unsigned int #define ull unsigned long long #define lll __int128 #define ld long double #define pb push_back #define mk make_pair #define ppcnt __builtin_popcount #define sort stable_sort const ll mod=(1ll<<31); ll read() { ll k=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } void write(char c){putchar(c);} int St[100],Top; void write(int x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } void write(ll x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } int prime[100010],cnt=0; ll f[100010],g[100010],mu[100010]; bitset<100000> vis; vector<pair<ll,ll>> vec; void init() { f[1]=g[1]=mu[1]=1; for(int i=2;i<=100000;++i) { if(!vis[i]) { prime[++cnt]=i; f[i]=g[i]=i+1; mu[i]=-1; } for(int j=1;j<=cnt&&i*prime[j]<=100000;++j) { vis[i*prime[j]]=1; if(i%prime[j]==0) { mu[i*prime[j]]=0; g[i*prime[j]]=g[i]*prime[j]+1; f[i*prime[j]]=f[i]/g[i]*g[i*prime[j]]; break; } g[i*prime[j]]=prime[j]+1; f[i*prime[j]]=f[i]*g[i*prime[j]]; mu[i*prime[j]]=-mu[i]; } } for(int i=1;i<=100000;++i)vec.pb(mk(f[i],i)); } struct Query { ll n,m,a; int id; }b[20010]; ll t[100010]; int lowbit(int x){return x&(-x);} void updata(int x,ll d) { while(x&&x<=100000) { t[x]+=d; x+=lowbit(x); } } ll query(int x) { ll res=0; while(x) { res+=t[x]; x-=lowbit(x); } return res; } ll ans[20010]; int main() { std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); init(); sort(vec.begin(),vec.end()); int q=read(); for(int i=1;i<=q;++i) { b[i].n=read(),b[i].m=read(),b[i].a=read(); if(b[i].n>b[i].m)swap(b[i].n,b[i].m); b[i].id=i; } sort(b+1,b+1+q,[](Query x,Query y){return x.a<y.a;}); for(int i=1,j=0;i<=q;++i) { while(j<100000&&vec[j].first<=b[i].a) { for(int k=vec[j].second;k<=100000;k+=vec[j].second) { updata(k,vec[j].first*mu[k/vec[j].second]); } ++j; } ll n=b[i].n,m=b[i].m,res=0; for(ll l=1,r;l<=n;l=r+1) { r=min({n,n/(n/l),m/(m/l)}); res+=(query(r)-query(l-1))*(n/l)%mod*(m/l)%mod; } ans[b[i].id]=res; } for(int i=1;i<=q;++i)write(ans[i]%mod),write('\n'); return 0; } ``` ## [F Luogu P3327](https://www.luogu.com.cn/problem/P3327) ### 题目 设 $d(x)$ 为 $x$ 的约数的个数，求 $$ \sum_{i = 1}^{n}{\sum_{j = 1}^{m}{d(ij)}} $$ $T , n , m \le 5 \times 10^4$。 ### Solution 首先这个题需要一个非常奇妙的转化 $$ d(ij) = \sum_{x | i}{\sum_{y | j}{[\gcd(x,y) = 1]}} $$ 显然对于每个质因子的贡献是独立的，于是，只需要考虑每个质因子的贡献即可。 对于某个质因子 $p$，它在 $i$ 中的出现次数是 $i_p$，在 $j$ 中的出现次数是 $j_p$，那么它在 $ij$ 的出现次数是 $i_p + j_p$，那它的贡献是 $i_p + j_p + 1$，而它满足 $\gcd(x,y) = 1$，就是它只能在某一个中出现，简单容斥得到贡献为 $i_p + j_p + 1$。 然后大力推式子 $$ \begin{align*} &\sum_{i = 1}^{n}{\sum_{j = 1}^{m}{d(ij)}} \\ &= \sum_{i = 1}^{n}{\sum_{j = 1}^{m}{\sum_{x | i}{\sum_{y | j}{[\gcd(x,y) = 1]}}}} \\ &= \sum_{x = 1}^{n}{\sum_{y = 1}^{m}{[\gcd(x,y) = 1] \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor}} \\ &= \sum_{x = 1}^{n}{\sum_{y = 1}^{m}{\lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor \sum_{k | x , k | y}{\mu(k)}}} \\ &= \sum_{k = 1}^{n}{\mu(k) \sum_{x = 1}^{\lfloor \frac{n}{k} \rfloor}{\sum_{y = 1}^{\lfloor \frac{m}{k} \rfloor}{\lfloor \frac{n}{xk} \rfloor \lfloor \frac{m}{yk} \rfloor}}} \\ &= \sum_{k = 1}^{n}{\mu(k) (\sum_{x = 1}^{\lfloor \frac{n}{k} \rfloor}{\lfloor \frac{\lfloor \frac{n}{k} \rfloor}{x} \rfloor}) (\sum_{y = 1}^{\lfloor \frac{m}{k} \rfloor}{\lfloor \frac{\lfloor \frac{m}{k} \rfloor}{y} \rfloor})} \end{align*} $$ 设 $$ f(x) = \sum_{i = 1}^{x}{\lfloor \frac{x}{i} \rfloor} $$ 那么原式化为 $$ \sum_{k = 1}^{n}{\mu(k) f(\lfloor \frac{n}{k} \rfloor) f(\lfloor \frac{m}{k} \rfloor)} $$ 然后预处理 $f$ 的值，做二维数论分块即可。 时间复杂度 $O(n \sqrt{n} + q \sqrt{n})$。 ### AC Code ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long #define uni unsigned int #define ull unsigned long long #define lll __int128 #define ld long double #define pb push_back #define mk make_pair #define ppcnt __builtin_popcount #define sort stable_sort ll read() { ll k=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } void write(char c){putchar(c);} int St[100],Top; void write(int x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } void write(ll x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } int prime[50010],cnt=0; bitset<50010> vis; int mu[50010]; ll f[50010]; void init() { mu[1]=1; for(int i=2;i<=50000;++i) { if(!vis[i]) { mu[i]=-1; prime[++cnt]=i; } for(int j=1;j<=cnt&&i*prime[j]<=50000;++j) { vis[i*prime[j]]=1; if(i%prime[j]==0) { mu[i*prime[j]]=0; break; } mu[i*prime[j]]=-mu[i]; } } for(int i=1;i<=50000;++i)mu[i]+=mu[i-1]; for(int n=1;n<=50000;++n) { for(int l=1,r;l<=n;l=r+1) { r=n/(n/l); f[n]+=1ll*(r-l+1)*(n/l); } } } void solve() { ll n=read(),m=read(); if(n>m)swap(n,m); ll ans=0; for(int l=1,r;l<=n;l=r+1) { r=min(n/(n/l),m/(m/l)); ans+=(mu[r]-mu[l-1])*f[n/l]*f[m/l]; } write(ans),write('\n'); } int main() { std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); init(); int T=read(); while(T--)solve(); return 0; } ``` ## [G Luogu P5150](https://www.luogu.com.cn/problem/P5150) ### 题目 给定 $n$，求有多少对正整数 $(i,j)$ 的 $\operatorname{lcm}$ 是 $n$。 $n \le 10^{16}$。 ### Solution 考虑质因数分解，$n = \prod_{p}{p^{n_p}}$，那么 $\operatorname{lcm}(i,j) = n$ 的充要条件是 $\forall p , \max(i_p,j_p) = n_p$，那么对于所有质数是独立的，简单容斥得到对于某一个质数的选择方案数是 $2 n_p + 1$，根据乘法原理求积即可。 时间复杂度 $O(\sqrt{n})$。 ### AC Code ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long #define uni unsigned int #define ull unsigned long long #define lll __int128 #define ld long double #define pb push_back #define mk make_pair #define ppcnt __builtin_popcount #define sort stable_sort ll read() { ll k=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } void write(char c){putchar(c);} int St[100],Top; void write(int x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } void write(ll x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } int main() { std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); ll n=read(),ans=1; for(ll i=2;i*i<=n;++i) { if(n%i!=0)continue; int cnt=0; while(n%i==0)n/=i,cnt++; ans*=2*cnt+1; } if(n>1)ans*=3; write(ans); return 0; } ``` ## [H Luogu P6222](https://www.luogu.com.cn/problem/P6222) [Luogu P6156](https://www.luogu.com.cn/problem/P6156)加强版 ### 题目 $$ \sum_{i = 1}^{n}{\sum_{j = 1}^{n}{(i + j)^k \gcd(i,j) \mu^2(\gcd(i,j))}} $$ 原题 $T = 1 , n \le 5 \times 10^6 , k \le 10^{18}$。 加强版 $T \le 10^4 , n \le 10^7 , k < 2^{31}$，并取模 $2^{32}$。 ### Solution 直接推式子 $$ \begin{align*} &\sum_{i = 1}^{n}{\sum_{j = 1}^{n}{(i + j)^k \gcd(i,j) \mu^2(\gcd(i,j))}} \\ &= \sum_{d = 1}^{n}{d \mu^2(d) \sum_{i = 1}^{n}{\sum_{j = 1}^{n}{(i + j)^k [\gcd(i,j) = d]}}} \\ &= \sum_{d = 1}^{n}{d \mu^2(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}{\sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor}{(id + jd)^k [\gcd(i,j) = 1]}}} \\ &= \sum_{d = 1}^{n}{d^{k + 1} \mu^2(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}{\sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor}{(i + j)^k [\gcd(i,j) = 1]}}} \\ &= \sum_{d = 1}^{n}{d^{k + 1} \mu^2(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}{\sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor}{(i + j)^k \sum_{x | i , x | j}{\mu(x)}}}} \\ &= \sum_{d = 1}^{n}{d^{k + 1} \mu^2(d) \sum_{x = 1}^{\lfloor \frac{n}{d} \rfloor}{\mu(x) x^k \sum_{i = 1}^{\lfloor \frac{n}{dx} \rfloor}{\sum_{j = 1}^{\lfloor \frac{n}{dx} \rfloor}{(i + j)^k}}}} \\ &= \sum_{t = 1}^{n}{(\sum_{d | t}{d^{k + 1} \mu^2(k) \mu(\frac{t}{d}) (\frac{t}{d})^k}) (\sum_{i = 1}^{\lfloor \frac{n}{t} \rfloor}{\sum_{j = 1}^{\lfloor \frac{n}{t} \rfloor}{(i + j)^k}})} \\ &= \sum_{t = 1}^{n}{t^k (\sum_{d | t}{d \mu^2(k) \mu(\frac{t}{d})}) (\sum_{i = 1}^{\lfloor \frac{n}{t} \rfloor}{\sum_{j = 1}^{\lfloor \frac{n}{t} \rfloor}{(i + j)^k}})} \end{align*} $$ 此时，$t^k$ 和第二个和式已经可以筛了，那么考虑第三个和式怎么处理。 令 $f(x) = \sum_{i = 1}^{x}{\sum_{j = 1}^{x}{(i + j)^k}}$，我们拆开式子后能发现 $$ f(x) - f(x - 1) = 2 \sum_{i = x + 1}^{2x}{i^k} - (2x)^k $$ 和式通过预处理前缀和递推即可。 此时就可以数论分块做了。 时间复杂度 $O(n + T \sqrt{n})$。 ### AC Code 普通版 ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long #define uni unsigned int #define ull unsigned long long #define lll __int128 #define ld long double #define pb push_back #define mk make_pair #define ppcnt __builtin_popcount #define sort stable_sort const ll mod=998244353; ll read() { ll k=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } void write(char c){putchar(c);} int St[100],Top; void write(int x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } void write(ll x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } ll fpow(ll x,ll y) { ll res=1; while(y) { if(y&1)res=res*x%mod; x=x*x%mod; y>>=1; } return res; } int prime[5000010],cnt=0; bitset<10000010> vis; ll idk[10000010],h[10000010],s[5000010]; void init(ll n,ll k) { idk[1]=h[1]=1; for(ll i=2;i<=n;++i) { if(!vis[i]) { prime[++cnt]=i; h[i]=i-1; idk[i]=fpow(i,k); } for(int j=1;j<=cnt&&i*prime[j]<=n;++j) { vis[i*prime[j]]=1; idk[i*prime[j]]=idk[i]*idk[prime[j]]%mod; if(i%prime[j]==0) { if((i/prime[j])%prime[j]!=0)h[i*prime[j]]=(mod-prime[j])*h[i/prime[j]]%mod; else h[i*prime[j]]=0; break; } h[i*prime[j]]=h[i]*h[prime[j]]%mod; } } for(int i=1;i<=n;++i)(h[i]*=idk[i])%=mod; for(int i=1;i<=n;++i)(h[i]+=h[i-1])%=mod; for(int i=1;i<=n;++i)(idk[i]+=idk[i-1])%=mod; for(int i=1;i<=n;++i)(idk[i]+=idk[i-1])%=mod; for(int i=1;i<=(n>>1);++i)s[i]=(idk[i*2]-2*idk[i]%mod+mod)%mod; } int main() { std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); ll n=read(),k=read(); init(n<<1,k); ll ans=0; for(ll l=1,r;l<=n;l=r+1) { r=min(n,n/(n/l)); (ans+=(h[r]-h[l-1])%mod*s[n/l]%mod)%=mod; } write((ans+mod)%mod); return 0; } ``` 加强版 ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long #define uni unsigned int #define ull unsigned long long #define lll __int128 #define ld long double #define pb push_back #define mk make_pair #define ppcnt __builtin_popcount #define sort stable_sort ll read() { ll k=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } void write(char c){putchar(c);} int St[100],Top; void write(int x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } void write(uni x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } uni fpow(uni x,ll y) { uni res=1; while(y) { if(y&1)res=res*x; x=x*x; y>>=1; } return res; } int prime[10000010],cnt=0; bitset<20000010> vis; uni idk[20000010],h[20000010],s[10000010]; void init(uni n,ll k) { idk[1]=h[1]=1; for(uni i=2;i<=n;++i) { if(!vis[i]) { prime[++cnt]=i; h[i]=i-1; idk[i]=fpow(i,k); } for(uni j=1;j<=cnt&&i*prime[j]<=n;++j) { vis[i*prime[j]]=1; idk[i*prime[j]]=idk[i]*idk[prime[j]]; if(i%prime[j]==0) { if((i/prime[j])%prime[j]!=0)h[i*prime[j]]=-prime[j]*h[i/prime[j]]; else h[i*prime[j]]=0; break; } h[i*prime[j]]=h[i]*h[prime[j]]; } } for(int i=1;i<=n;++i)h[i]*=idk[i]; for(int i=1;i<=n;++i)h[i]+=h[i-1]; for(int i=1;i<=n;++i)idk[i]+=idk[i-1]; for(int i=1;i<=n;++i)idk[i]+=idk[i-1]; for(int i=1;i<=(n>>1);++i)s[i]=idk[i*2]-2*idk[i]; } ll k; void solve() { uni n=read(); uni ans=0; for(uni l=1,r;l<=n;l=r+1) { r=min(n,n/(n/l)); ans+=(h[r]-h[l-1])*s[n/l]; } write(ans),write('\n'); } int main() { std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T=read(); uni N=read(); k=read(); init(N<<1,k); while(T--)solve(); return 0; } ``` ## [I AT_agc038_c](https://atcoder.jp/contests/agc038/tasks/agc038_c) ### 题目 给定 $n$ 个正整数 $a_1 \cdots a_n$，求 $$ \sum_{i = 1}^{n - 1}{\sum_{j = i + 1}^{n}{\operatorname{lcm}(a_i,a_j)}} $$ $n \le 2 \times 10^5 , a_i \le 10^6$。 ### Solution 首先发现式子不齐，于是补齐在考虑容掉。 然后答案变为 $$ Ans = \frac{\sum_{i = 1}^{n}{\sum_{j = 1}^{n}{\operatorname{lcm}(a_i,a_j)}} - \sum_{i = 1}^{n}{a_i}}{2} $$ 然后我们只需要处理第一个和式。 发现值域很小，于是开桶，用 $c_i$ 表示有多少数为 $i$。 然后大力推式子，用 $V$ 表示值域范围 $$ \begin{align*} &\sum_{i = 1}^{n}{\sum_{j = 1}^{n}{\operatorname{lcm}(a_i,a_j)}} \\ &= \sum_{i = 1}^{V}{\sum_{j = 1}^{V}{\operatorname{lcm}(i,j) c_i c_j}} \\ &= \sum_{i = 1}^{V}{\sum_{j = 1}^{V}{i j c_i c_j \gcd(i,j)^{-1}}} \\ &= \sum_{d = 1}^{V}{d^{-1} \sum_{i = 1}^{V}{\sum_{j = 1}^{V}{i j c_i c_j [\gcd(i,j) = d]}}} \\ &= \sum_{d = 1}^{V}{d^{-1} \sum_{i = 1}^{\lfloor \frac{V}{d} \rfloor}{\sum_{j = 1}^{\lfloor \frac{V}{d} \rfloor}{id jd c_{id} c_{jd} [\gcd(i,j) = 1]}}} \\ &= \sum_{d = 1}^{V}{d \sum_{i = 1}^{\lfloor \frac{V}{d} \rfloor}{\sum_{j = 1}^{\lfloor \frac{V}{d} \rfloor}{i j c_{id} c_{id} \sum_{k | i , k | j}{\mu(k)}}}} \\ &= \sum_{d = 1}^{V}{d \sum_{k = 1}^{\lfloor \frac{V}{d} \rfloor}{ \mu(k) \sum_{i = 1}^{\lfloor \frac{V}{dk} \rfloor}{\sum_{j = 1}^{\lfloor \frac{V}{dk} \rfloor}{i j c_{idk} c_{jdk}}}}} \\ &= \sum_{d = 1}^{V}{d \sum_{k = 1}^{\lfloor \frac{V}{d} \rfloor}{\mu(k) (\sum_{i = 1}^{\lfloor \frac{V}{dk} \rfloor}{i c_{idk}})^2}} \\ &= \sum_{t = 1}^{V}{(\sum_{d | t}{d \mu(\frac{t}{d})}) (\sum_{i = 1}^{\lfloor \frac{V}{t} \rfloor}{i c_{it}})^2} \end{align*} $$ 现在，我们发现第一个和式是一个积性函数，直接筛即可。第二个是一个调和级数复杂度预处理的东西，最后枚举 $t$ 统计答案即可。 时间复杂度 $O(V \ln V)$。 ### AC Code ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long #define uni unsigned int #define ull unsigned long long #define lll __int128 #define ld long double #define pb push_back #define mk make_pair #define ppcnt __builtin_popcount #define sort stable_sort const ll mod=998244353,inv2=499122177; ll read() { ll k=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } void write(char c){putchar(c);} int St[100],Top; void write(int x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } void write(ll x) { if(x==0){putchar('0');return;} if(x<0)putchar('-'),x=-x; Top=0;while(x)St[++Top]=x%10,x/=10; while(Top)putchar((char)('0'+St[Top--])); } int n,ma=0; ll c[1000010]; ll sum=0; int cnt=0,prime[1000010]; bitset<1000010> vis; ll mu[1000010],f[1000010],g[1000010]; void init() { mu[1]=1; for(int i=2;i<=ma;++i) { if(!vis[i]) { prime[++cnt]=i; mu[i]=-1; } for(int j=1;j<=cnt&&i*prime[j]<=ma;++j) { vis[i*prime[j]]=1; if(i%prime[j]==0) { mu[i*prime[j]]=0; break; } mu[i*prime[j]]=-mu[i]; } } for(int i=1;i<=ma;++i)mu[i]*=i; for(int i=1;i<=ma;++i)for(int j=i;j<=ma;j+=i)(f[j]+=mu[i])%=mod; for(int t=1;t<=ma;++t)for(int i=1;i<=ma/t;++i)(g[t]+=i*c[i*t]%mod)%=mod; for(int i=1;i<=ma;++i)g[i]=g[i]*g[i]%mod; } int main() { std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); memset(c,0,sizeof(c)); n=read(); for(int i=1;i<=n;++i) { int a=read(); c[a]++; ma=max(ma,a); sum+=a; } init(); ll ans=0; for(int i=1;i<=ma;++i)(ans+=i*f[i]%mod*g[i]%mod)%=mod; (ans-=sum)%=mod; ans=ans*inv2%mod; write((ans+mod)%mod); return 0; } ```