首页 > 代码库 > BZOJ2694: Lcm

BZOJ2694: Lcm

2024-11-01 15:41:39   207人阅读

题目：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即可。

代码：

技术分享
  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 1000000000 24  25 #define maxn 4000000+5 26  27 #define maxm 4000000 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));111             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

 

BZOJ2694: Lcm


联系
我们