本文共 1272 字，大约阅读时间需要 4 分钟。

Description

求 $\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$ Input 一个正整数T表示数据组数 接下来T行 每行两个正整数 表示N、M Output T行 每行一个整数 表示第i组数据的结果 Sample Input 1 4 5 Sample Output 122 HINT T <= 10000 N, M<=10000000 题解： 普通的化法可以变成

$$\sum_{d=1}^{n}d\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\frac{x^2\mu(x)sum(\lfloor\frac{n}{dx}\rfloor,\lfloor\frac{m}{d}\rfloor)}{4}$$ sum(x,y)=x(x+1)y(y+1) 设T=dx; 则可以化成 $$\sum_{T=1}^{n}sum2(\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor)T\sum_{x|T}^{}\mu(x)x$$ sum2(x,y)=x(x+1)y(y+1)/4 设f(T)= ∑x|Tμ(x)x $\sum_{x|T}^{}\mu(x)x$ 如果我们能与处理出f数组,然后做一个Tf(T)的前缀和即可。 可以证明f(T)是积性函数.然后我们把f(T)线筛出来即可。

#include
   
    #include
    
     #include
     
      #define N 10000010#define P 100000009#define LL long longusing namespace std;int p[N],f[N],n,m,T,pos;LL g[N],ans,s[N];void pre(){  g[1]=1;  for (int i=2;i<=n;i++){    if (!f[i]){p[++p[0]]=i;g[i]=(1-i+P)%P;}    for (int j=1;j<=p[0]&&i*p[j]<=n;j++){      f[i*p[j]]=1;      if (i%p[j]==0){g[i*p[j]]=g[i];break;}      g[i*p[j]]=(g[i]*g[p[j]])%P;    }  }  for (int i=1;i<=n;i++) g[i]=(g[i]*i)%P;  for (int i=1;i<=n;i++) s[i]=(s[i-1]+g[i])%P;}LL sum(LL x,LL y){  LL t1=x*(x+1)/2;LL t2=y*(y+1)/2;  t1%=P;t2%=P;  return (t1*t2)%P; }int main(){     scanf("%d",&T);n=N-10;pre();     while (T--){     scanf("%d%d",&n,&m);     if (n>m) swap(n,m);ans=0;pos=0;     for (int i=1;i<=n;i=pos+1){       pos=min((n/(n/i)),(m/(m/i)));       ans+=(sum((LL)(n/i),(LL)(m/i))*(s[pos]-s[i-1]+P)%P)%P;       ans%=P;     }       printf("%lld\n",ans);     }}
     
    
   

转载地址：https://blog.csdn.net/sunshinezff/article/details/50952611 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！