【51Nod1227】平均最小公倍数-杜教筛

测试地址:平均最小公倍数
做法:这一题需要用到杜教筛。这一题推式子的过程比较经典,是做杜教筛更难题的基础。

首先定义几个接下来要用到的符号和函数:
幂函数:idk(n)=nk(完全积性)
lcm(i,j)gcd(i,j)ij的最小公倍数和最大公约数(这个不懂就……)
函数fg的狄利克雷卷积:fg(fg)(n)=d|nf(d)g(n/d)
函数fg的普通乘法:fg(fg)(n)=f(n)g(n)
[S]:若式子S为真则[S]=1,否则[S]=0

我们用公式表达要求的函数:A(n)=1nni=1lcm(n,i),求F(n)=ni=1A(i)A不是积性函数,所以我们要想办法将式子化成积性函数前缀和的形式。
我们知道lcm(i,j)×gcd(i,j)=ij,所以A(n)=1nni=1nigcd(n,i)=ni=1igcd(n,i)。但是igcd(n,i)仍然不是积性的,所以我们进行进一步化简:

A(n)=i=1nigcd(n,i)=i=1nd|n[gcd(n,i)=d]×id=d|nid=1nd[gcd(nd,id)=1]×id

注意到n/di/d=1[gcd(nd,id)=1]×id其实就是问小于等于nd的数中和它互质的数的和,又因为如果ix互质,那么xi也和x互质(这个很显然,随便证证就可以了),推测出小于等于x的与x互质的数是成对出现的,而且每一对的贡献都是x,所以小于等于x的与x互质的数的和为x×φ(x)×12,特别地,小于等于1的与1互质的数的和为1(若用上面公式算将算出12),代入上面的式子中得:
A(n)=12(1+d|nd×φ(d))

我们发现这个式子已经有点积性函数的意思了,我们再用这个式子来算F(n)
F(n)=i=1nA(i)=12(n+i=1nd|id×φ(d))=12(n+i=1nd=1nid×φ(d))

那么G(n)=ni=1i×φ(i)就是一个积性函数前缀和了。
要求函数idφ的前缀和,考虑卷上一个好算前缀和的函数,从而得到另一个好算前缀和的函数。显然(idφ)id=id2,因为d|nd×φ(d)×nd=nd|nφ(d)=n2,那么:
n(n+1)(2n+1)6=i=1ni2=i=1nd|id×φ(d)×id=id=1nidd=1nidd×φ(d)=i=1ni×G(ni)

看不懂上述式子的同学可以尝试从约数、倍数和贡献的方面来理解一下……
G(n)一项提出来,得:
G(n)=n(n+1)(2n+1)6i=2ni×G(ni)

再结合这个式子:
F(n)=12(n+i=1nG(ni))

这样就可以使用杜教筛来计算了,使用哈希表判重,再预处理前n23G值,就可以达到O(n23)的时间复杂度了。注意因为答案要模109+7,所以不能直接将结果乘上12,而应该乘上2关于模109+7的逆元:5×108+4
以下是本人代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define hashsize 5000000
#define limit 1000000
#define mod 1000000007
#define ll long long
using namespace std;
ll a,b,phi[limit+5],sum[limit+5],h[hashsize+5]={0},f[hashsize+5];
bool prime[limit+5]={0};

int hash(ll x)
{
  ll s=x%hashsize;
  while(h[s]&&h[s]!=x) s=(s+1)%hashsize;
  return s;
}

void init()
{
  for(int i=1;i<=limit;i++) phi[i]=i;
  for(ll i=2;i<=limit;i++)
    if (!prime[i])
    {
      for(ll j=1;i*j<=limit;j++)
      {
        prime[i*j]=1;
        phi[i*j]=phi[i*j]/i*(i-1);
      }
    }
  sum[0]=0;
  for(int i=1;i<=limit;i++)
    sum[i]=(sum[i-1]+i*phi[i])%mod;
}

ll gcd(ll a,ll b)
{
  return (b==0)?a:gcd(b,a%b);
}

ll sum1(ll a,ll b)
{
  return (b*(b+1)/2-a*(a-1)/2)%mod;
}

ll sum2(ll x)
{
  ll a=x,b=x+1,c=2*x+1,s=6,g;
  g=gcd(a,s),a/=g,s/=g;
  g=gcd(b,s),b/=g,s/=g;
  g=gcd(c,s),c/=g,s/=g;
  return (((a*b)%mod)*c)%mod;
}

ll G(ll x)
{
  if (x<=limit) return sum[x];
  int pos=hash(x);
  if (h[pos]==x) return f[pos];
  ll i=2,next,s=0;
  while(i<=x)
  {
    next=x/(x/i);
    s=(s+sum1(i,next)*G(x/i))%mod;
    i=next+1;
  }
  h[pos]=x,f[pos]=(sum2(x)-s+mod)%mod;
  return f[pos];
}

ll F(ll x)
{
  ll i=1,next,s=0;
  while(i<=x)
  {
    next=x/(x/i);
    s=(s+(next-i+1)*G(x/i))%mod;
    i=next+1;
  }
  return (500000004*(s+x))%mod;
}

int main()
{
  init();
  scanf("%lld%lld",&a,&b);
  printf("%lld",(F(b)-F(a-1)+mod)%mod);

  return 0;
}
原文地址:https://www.cnblogs.com/Maxwei-wzj/p/9793627.html