BZOJ 2694: Lcm [莫比乌斯反演线性筛]

题意：求$\sum\limits_{i=1}^n \sum\limits_{j=1}^m lcm(i,j)\ : gcd(i,j) 是sf 无平方因子数$

无平方因子数？搞一个$\mu(gcd(i,j))$不就行了..不对不对有正负，是$\mu^2$才行

套路推♂倒 (ﾉ*･ω･)ﾉ

\[\begin{align*}
\sum\limits_{i=1}^n \sum\limits_{j=1}^m \frac{ij}{gcd(i,j)} \mu(gcd(i,j))^2
&=\sum_{d=1}^n d\ \mu(d^2) \sum_{i=1}^{\frac{n}{d}} \sum_{j=1}^{\frac{m}{d}}ij[gcd(i,j)=1]\\
&= \sum_{D=1}^n D\sum_{d|D} \mu(d)^2 \mu(\frac{D}{d})\frac{D}{d} \ f(\frac{n}{D}, \frac{m}{D}) \\
\end{align*}
\]

woc那是个smg，自己卷自己？ $g(i) = i \cdot ((\mu \cdot \mu) * (\mu \cdot id))(i) $

如果我没猜错，点乘和卷积没有什么律吧

$g(1) = 1$

$g(p) = p*(1-p)$

观察那堆$\mu$，分成的两个因子都有的话，相同的质数必须一边一个啊要不就是0没贡献了

考虑$p \mid i$，$i$中还至少有一个$p$，我们记录最小质因子的次数判断一下$ip$的质因子多于2个$g(ip)=0$了，正好两个的话肯定是一面一个，结果就是$g(\frac{i}{p})*(-p)$啊...不对不对，前面的$i$让你吃了？应该是$*(-p\cdot p^2)$

貌似还有更科学的想法，i除掉p后两个就互质了...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int N=4e6+5, INF=1e9, P = 1<<30;

#define pii pair<int, int>

#define MP make_pair

#define fir first

#define sec second

typedef long long ll;

inline int read(){

    char c=getchar();int x=0,f=1;

    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    return x*f;

}

int n, m;

int notp[N], p[N], cp[N]; ll g[N];

void sieve(int n) {

    g[1] = 1;

    for(int i=2; i<=n; i++) {

        if(!notp[i]) p[++p[0]] = i, g[i] = i*(1-i), cp[i] = 1;

        for(int j=1; j<=p[0] && i*p[j]<=n; j++) {

            int t = i*p[j];

            notp[t] = 1;

            if(i%p[j] == 0) {

                cp[t] = cp[i]+1;

                if(cp[t] <= 2) g[t] = g[i/p[j]] * (-p[j] * p[j] * p[j]) %P;

                else g[t] = 0;

                break;

            }

            cp[t] = 1;

            g[t] = g[i] * g[p[j]];

        }

    }

    for(int i=1; i<=n; i++) (g[i] += g[i-1]) %=P;

}

inline ll f(ll n, ll m) {return ( n*(n+1)/2 %P) * ( m*(m+1)/2 %P)%P;}

ll cal(int n, int m) {

    ll ans=0; int r;

    for(int i=1; i<=n; i=r+1) {

        r = min(n/(n/i), m/(m/i));

        ( ans += (g[r] - g[i-1]) * f(n/i, m/i) )%=P;

    }

    return (ans+P)%P;

}

int main() {

    //freopen("in","r",stdin);

    sieve(N-1);

    int T=read();

    while(T--) {

        n=read(); m=read();

        if(n>m) swap(n, m);

        printf("%lld\n", cal(n, m));

    }

}

巴特西

BZOJ 2694: Lcm [莫比乌斯反演线性筛]

最新文章

热门文章

巴特西

BZOJ 2694: Lcm [莫比乌斯反演 线性筛]

最新文章

热门文章

BZOJ 2694: Lcm [莫比乌斯反演线性筛]