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);
    }
}