首页 > 代码库 > BZOJ2694: Lcm
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即可。
代码：
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 }
BZOJ2694: Lcm
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。