差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:数论_2 [2020/07/04 22:52]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:数论_2 [2020/07/27 22:56] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:数论_2被移动至2020-2021:teams:legal_string:jxm2001:数论_2
@@ 行 320: / 行 320: @@
 \begin{equation}\sum_{d\mid k}^{k\le min(a,b)}\mu (\lfloor \frac kd\rfloor)\lfloor\frac ak\rfloor\lfloor \frac bk\rfloor=\sum_{t=1}^{t\ast d\le \min(a,b)}\mu (t)\lfloor\frac a{t\ast d}\rfloor\lfloor \frac b{t\ast d}\rfloor\end{equation}
-剩下部分数论分块即可，时间复杂度 $O\left(\max\left(\sqrt a,\sqrt b\right)\right)$。
+剩下部分数论分块即可，时间复杂度 $O(\sqrt n)$。
 <hidden 查看代码>
 <code cpp>
-#include <cstdio>
-#include <iostream>
-#include <vector>
-#include <algorithm>
-#include <cstring>
-#include <cctype>
-#include <queue>
-#include <cmath>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset((a),(b),sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXP=5e4+5;
 bool vis[MAXP];
@@ 行 417: / 行 383: @@
 \begin{equation}\sum_i^{\lfloor\frac ad\rfloor}\sum_j^{\lfloor\frac bd\rfloor}\sum_{k\mid(i,j)}\mu(k)=\sum_{k=1}^{\min(\lfloor\frac ad\rfloor,\lfloor\frac bd\rfloor)}\sum_{k\mid i}^{i\le\lfloor\frac ad\rfloor}\sum_{k\mid j}^{j\le\lfloor\frac bd\rfloor}\mu(k)=\sum_{k=1}^{\min(\lfloor\frac ad\rfloor,\lfloor\frac bd\rfloor)}\lfloor\frac{\lfloor\frac ad\rfloor}k\rfloor\lfloor\frac{\lfloor\frac bd\rfloor}k\rfloor\mu(k)\end{equation}
-剩下部分数论分块即可，时间复杂度 $O\left(\max\left(\sqrt a,\sqrt b\right)\right)$。
+剩下部分数论分块即可，时间复杂度 $O(\sqrt n)$。
 <hidden 查看代码>
 <code cpp>
-#include <cstdio>
-#include <iostream>
-#include <vector>
-#include <algorithm>
-#include <cstring>
-#include <cctype>
-#include <queue>
-#include <cmath>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset((a),(b),sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXP=5e4+5;
 bool vis[MAXP];
@@ 行 561: / 行 493: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXP=5e4+5;
 bool vis[MAXP];
@@ 行 658: / 行 543: @@
 	}
 	return 0;
+}
+</code>
+</hidden>
+==== 习题3 ====
+[[https://www.luogu.com.cn/problem/P3704|洛谷p3704]]
+=== 题意 ===
+共 $T$ 组询问，每次询问 $\prod_{i=1}^n\prod_{j=1}^mf_{\text{gcd}(i,j)}\bmod p$，其中 $f$ 表示斐波那契数列，且$f_0=0,f_1=1$。
+=== 题解 ===
+不妨设 $n\le m$。
+首先按套路把 $\text{gcd}$ 换成莫比乌斯函数，有
+\begin{equation}\prod_{i=1}^n\prod_{j=1}^mf_{\text{gcd}(i,j)}=\prod_{d=1}^n\prod_{i=1}^n\prod_{j=1}^mf_d[(i,j)==d]=\prod_{d=1}^nf_d^{\sum_{i=1}^n\sum_{j=1}^m[(i,j)==d]}=\prod_{d=1}^n f_d^{\sum_{k=1}^{\lfloor\frac nd\rfloor}\mu(k)\lfloor\frac n{kd}\rfloor\lfloor\frac m{kd}\rfloor}\end{equation}
+令 $T=kd$，有
+\begin{equation}\prod_{d=1}^n f_d^{\sum_{k=1}^{\lfloor\frac nd\rfloor}\mu(k)\lfloor\frac n{kd}\rfloor\lfloor\frac m{kd}\rfloor}=\prod_{T=1}^n\left(\prod_{d\mid T}f_d^{\mu(\frac Td)}\right)^{\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor}\end{equation}
+外部指数部分考虑数论分块。内部可以先预处理，枚举 $d$，对每个 $T=kd$ 计算贡献。
+预处理时间复杂度 $O(n\log p+\sum_{i=1}^n \frac ni)=O(n(\log n+\log p))$，询问的时间复杂度为 $O(T\sqrt n\log p)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e6+5,mod=1e9+7;
+bool vis[MAXN];
+int prime[MAXN],mu[MAXN],f[MAXN],s[MAXN],s_inv[MAXN],cnt;
+int quick_pow(int a,int b){
+	LL t=1;
+	while(b){
+		if(b&1)
+		t=t*a%mod;
+		a=1LL*a*a%mod;
+		b>>=1;
+	}
+	return t%mod;
+}
+void Pre(){
+	vis[1]=true,mu[1]=1;f[0]=0,f[1]=1;
+	_for(i,2,MAXN){
+		f[i]=(f[i-2]+f[i-1])%mod;
+		if(!vis[i])mu[i]=-1,prime[cnt++]=i;
+		for(int j=0;j<cnt&&i*prime[j]<MAXN;j++){
+			vis[i*prime[j]]=true;
+			if(i%prime[j])
+			mu[i*prime[j]]=-mu[i];
+			else{
+				mu[i*prime[j]]=0;
+				break;
+			}
+		}
+	}
+	_for(i,0,MAXN)
+	s[i]=s_inv[i]=1;
+	int base[3]={1,1,1},*t=base+1;
+	_for(i,2,MAXN){
+		t[-1]=quick_pow(f[i],mod-2),t[1]=f[i];
+		for(int j=1;j*i<MAXN;j++){
+			s[i*j]=1LL*s[i*j]*t[mu[j]]%mod;
+			s_inv[i*j]=1LL*s_inv[i*j]*t[-mu[j]]%mod;
+		}
+	}
+	_for(i,2,MAXN)
+	s[i]=1LL*s[i]*s[i-1]%mod,s_inv[i]=1LL*s_inv[i]*s_inv[i-1]%mod;
+}
+int cal(int n,int m){
+	int lef=1,rig;
+	LL ans=1;
+	while(lef<=n){
+		rig=min(n/(n/lef),m/(m/lef));
+		ans=ans*quick_pow(1LL*s[rig]*s_inv[lef-1]%mod,1LL*(n/lef)*(m/lef)%(mod-1))%mod;
+		lef=rig+1;
+	}
+	return (ans+mod)%mod;
+}
+int main()
+{
+	int t=read_int(),n,m;
+	Pre();
+	while(t--){
+		n=read_int(),m=read_int();
+		enter(cal(min(n,m),max(n,m)));
+	}
+    return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具