BZOJ2694: Lcm

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=2694

题解:令f[i]表示i是否有平方因子,则f[i]是积性函数,mu[i]表示莫比乌斯函数。

经过balabala的推导,我们得出ans=sigma(f[i/j]*mu[j]*j*j*sum(n/i,m/i)))  sum(x,y)=x*(x+1)/2*y*(y+1)/2

然后我们定义新函数 g[i]=sigma(f[i/d]*mu[d]*d*d) 因为积性函数的狄利克雷卷积仍然是积性函数,所以我们考虑把g数组线筛出来,然后就可以做到sqrt(n)回答询问了。

考虑i%p[j]==0的这部分(初值和i%p[j]!=0可以很简单算出来),如果k=i*p[j]中有p[j]的次数超过2,那么g[k]=0

这是因为我们要在f 和 mu 上分 p[j]的指数,>2时由鸽巢原理知必有一个分到2个以上,那么乘积就是0.

否则 p[j] 的指数为2,我们必须在 f 上分一个,mu上分一个,这样g[k]=g[i/p[j]]*-p[j]*p[j]*p[j]   (第一个p[j]是分到f上的,负号是给 mu 的,p[j]*p[j]则是d*d,还是利用了积性函数的性质)

既然是积性函数并且i/p[j]和p[j]*p[j]互质,那么g[k]就等于g[t]*g[p[j]*p[j]]  注意t==1时要特判。

然后这题就做完了。

因为模数奇特所以直接爆int即可。

代码:

BZOJ2694: Lcm
BZOJ2694: Lcm
  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1
 24 
 25 #define maxn 4+5
 26 
 27 #define maxm 4
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
 44 
 45 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
 46 
 47 #define mod 1073741823
 48 
 49 using namespace std;
 50 
 51 inline int read()
 52 
 53 {
 54 
 55     int x=0,f=1;char ch=getchar();
 56 
 57     while(ch<'0'ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 58 
 59     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 60 
 61     return x*f;
 62 
 63 }
 64 int tot,p[maxn],g[maxn];
 65 bool v[maxn];
 66 void get()
 67 {
 68     g[1]=1;
 69     for2(i,2,maxm)
 70     {
 71         if(!v[i])p[++tot]=i,g[i]=i-i*i;
 72         for1(j,tot)
 73         {
 74             int k=i*p[j];
 75             if(k>maxm)break;
 76             v[k]=1;
 77             if(i%p[j])g[k]=g[i]*g[p[j]];
 78             else 
 79             {
 80                 int t=i/p[j];
 81                 if(t%p[j]==0)g[k]=0;
 82                 else g[k]=-g[t]*p[j]*p[j]*p[j];
 83                 break;
 84             }
 85         }
 86     }
 87     for1(i,maxm)g[i]+=g[i-1];
 88 }
 89 inline int sum(int n,int m)
 90 {
 91     return n*(n+1)*m*(m+1)/4;
 92 }
 93 
 94 int main()
 95 
 96 {
 97 
 98     freopen("input.txt","r",stdin);
 99 
100     freopen("output.txt","w",stdout);
101     get();
102 
103     int T=read();
104     while(T--)
105     {
106         int n=read(),m=read(),ans=0;
107         if(n>m)swap(n,m);
108         for(int i=1,j;i<=n;i=j+1)
109         {
110             j=min(n/(n/i),m/(m/i));
             ans+=sum(n/i,m/i)*(g[j]-g[i-1]);
112         }
113         printf("%d\n",ans&mod);
114     }
115 
116     return 0;
117 
118 }  
View Code

 

更多相关文章
一周排行