bzoj 2694: Lcm （反演）

题目描述

传送门

题目大意：

定义整数a,b,求所有满足条件的lcm(a,b)的和：

1<=a<=A

1<=b<=B

∀n>1,n2†gcd(a,b)

输出答案对2^30取模。

题解

要求gcd(a,b)不能含平方因子，所以gcd(a,b)一定是mu不等于0的数。

那么我们设所有满足条件的数为p，n<=m

就可以将上述条件转化成式子

∑p∑i=1n∑j=1mlcm(a,b)[gcd(a,b)=p]

∑p∑i=1n∑j=1mi∗jp[gcd(a,b)=p]

∑pp∑d=1nμ(d)∗d2sum(⌊nd∗p⌋,⌊md∗p⌋)

其中 sum(x,y)=x∗(x+1)2∗y∗(y+1)2

设T=d*p

∑T=1nsum(⌊nT⌋,⌊mT⌋)∑p|Tμ(Tp)∗(Tp)2∗p

这个式子的话，要求 h(T)=∑p|Tμ(Tp)∗(Tp)2∗p

我们其实可以直接枚举mu不等于0的数，然后用它更新它的倍数，这样的时间复杂度应该均摊是不超过 O(nlogn)

还有这道题的模数非常特殊，是2的整数次幂，所以我们直接用int自然溢出，最后取模即可。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 4000003
using namespace std;
const int p=<<;
int n,m,T,prime[N+],pd[N+],mu[N+];
int f[N+];
void init()
{
    mu[]=;
    for (int i=;i<=N;i++) {
        if (!pd[i]) {
            prime[++prime[]]=i;
            mu[i]=-;
        }
        for (int j=;j<=prime[];j++) {
            int t=i*prime[j];
            if (t>N) break;
            pd[t]=;
            if (i%prime[j]==) {
                mu[t]=;
                break;
            }
            mu[t]=-mu[i];
        }
    }
    for (int i=;i<=N;i++) 
      if (mu[i]){
        int t=i;
        for (int j=;j*t<=N;j++) f[j*t]=f[j*t]+mu[j]*j*j*i;
    }
    for (int i=;i<=N;i++) f[i]=f[i]+f[i-];
}
int calc(int x,int y)
{
    int t1=(x+)*x>>; int t2=(y+)*y>>;
    return t1*t2;
}
int main()
{
    freopen("a.in","r",stdin);
    freopen("my.out","w",stdout);
    scanf("%d",&T); init();
    while (T--)
    {
      scanf("%d%d",&n,&m);
      if (n>m) swap(n,m);
      int ans=;
      for (int i=,j;i<=n;i=j+) {
        j=min(n/(n/i),m/(m/i));
        ans=ans+(f[j]-f[i-])*calc(n/i,m/i);
      }
      printf("%d\n",(ans%p+p)%p);
    }
}