「MCOI-02」Convex hull 凸包 题解

· · 题解

验题人写的一个题解，感觉比出题人的式子简单多了，而且用不着莫反。

\sum_{i\le n}\sum_{j\le m}\tau(i)\tau(j)\tau(\gcd(i,j))

考虑\tau的定义，有：

=\sum_{i\le n}\sum_{j\le m}\tau(i)\tau(j)\sum_{k|i,k|j}1

枚举k：

=\sum_k\sum_{k|i,i\le n}\tau(i)\sum_{k|j,j\le m}\tau(j)

设

S_n(k)=\sum_{k|i,i\le n}\tau(i)

则

(*)=\sum_kS_n(k)S_m(k)

式子推完了！

先在 O(n\log n) 时间内暴力预计算出 \tau(i),1\le i\le n，然后可以在 O(n\log n) 时间内暴力预计算出 S_n(k),S_m(k)，总复杂度 O(n\log n)。

放个代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int n,m,p,d[N],ans;
void init(int n){
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)
            d[j]++;
}
inline int calc(int n,int k){
    int ret=0;
    for(int i=k;i<=n;i+=k)ret=(ret+d[i])%p;
    return ret;
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    if(n>m)swap(n,m);
    init(m);
    for(int i=1;i<=n;i++)ans=(ans+1LL*calc(n,i)*calc(m,i)%p)%p;
    printf("%d\n",ans);
    return 0;
}