差别

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

--- 2020-2021:teams:legal_string:jxm2001:数论_2 [2020/07/04 11:50]
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];
@@ 行 498: / 行 430: @@
 </code>
 </hidden>
+比较题解 1 与题解 2 最后的式子，发现
+\begin{equation}\sum_{k=1}^{k\ast d\le \min(a,b)}\lfloor\frac a{k\ast d}\rfloor\lfloor \frac b{k\ast d}\rfloor=\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\tag{10}\end{equation}
 ==== 习题2 ====
@@ 行 509: / 行 445: @@
 === 引理 ===
-\begin{equation}\tau(ij)=\sum_{x\mid i}\sum_{y\mid j}[(i,j)==1]\end{equation}
+\begin{equation}\tau(ij)=\sum_{x\mid i}\sum_{y\mid j}[(x,y)==1]\tag{11}\end{equation}
 == 证明 ==
 设 $ij=p_1^{\alpha_1}p_2^{\alpha_2}... p_k^{\alpha_k},i=p_1^{\beta_1}p_2^{\beta_2}... p_k^{\beta_k}$，对每个 $ij$ 的因子 $z=p_1^{z_1}p_2^{z_2}... p_k^{z_k}$，构造如下映射
+\begin{equation}\begin{pmatrix}z_1&z_2&\cdots &z_k\\ \end{pmatrix}\longleftrightarrow\begin{pmatrix}x_1&x_2&\cdots &x_k\\y_1&y_2&\cdots &y_k\\ \end{pmatrix},\text{其中}\left \{
+\begin{array}{l}
+x_i=[z_i\le \beta_i]z_i \\
+y_i=[z_i\gt \beta_i](z_i-\beta_i)
+\end{array}
+\right.\end{equation}
+容易验证这是个双射，所以枚举 $z$ 等价于枚举 $x=p_1^{x_1}p_2^{x_2}... p_k^{x_k},y=p_1^{y_1}p_2^{y_2}... p_k^{y_k},x\mid i,y\mid j,(x,y)=1$，证毕。
+顺便给出式子\begin{equation}\varphi(ij)=\sum_{x\mid i}\sum_{y\mid j}\frac{iy}x[(x,y)==1]\tag{12}\end{equation}
+证明方法为构造如下映射
+\begin{equation}\begin{pmatrix}z_1&z_2&\cdots &z_k\\ \end{pmatrix}\longleftrightarrow\begin{pmatrix}x_1&x_2&\cdots &x_k\\y_1&y_2&\cdots &y_k\\ \end{pmatrix},\text{其中}\left \{
+\begin{array}{l}
+x_i=[z_i\le \beta_i](\beta_i-z_i) \\
+y_i=[z_i\gt \beta_i](z_i-\beta_i)
+\end{array}
+\right.\end{equation}
+容易验证这是个双射，且 $z=\frac{iy}x$。
 === 题解 ===
+根据引理，同时改变枚举顺序有\begin{equation}\sum_{i=1}^n\sum_{j=1}^m\tau(ij)=\sum_{i=1}^n\sum_{j=1}^m\sum_{x\mid i}\sum_{y\mid j}[(x,y)==1]=\sum_{x=1}^n\sum_{y=1}^m\lfloor\frac nx\rfloor\lfloor\frac my\rfloor[(x,y)==1]\end{equation}
+根据 $(6)$ 式并再次改变枚举顺序有
+\begin{equation}\sum_{x=1}^n\sum_{y=1}^m\lfloor\frac nx\rfloor\lfloor\frac my\rfloor[(x,y)==1]=\sum_{x=1}^n\sum_{y=1}^m\lfloor\frac nx\rfloor\lfloor\frac my\rfloor\sum_{d=1}^{(x,y)}\mu(d)=\sum_{d=1}^{\min(n,m)}\sum_{d\mid x}^{x\le n}\sum_{d\mid y}^{y\le m}\lfloor\frac nx\rfloor\lfloor\frac my\rfloor\mu(d)\end{equation}
+改为枚举倍数，再根据 $(10)$ 式有
+\begin{equation}\sum_{d=1}^{\min(n,m)}\sum_{d\mid x}^{x\le n}\sum_{d\mid y}^{y\le m}\lfloor\frac nx\rfloor\lfloor\frac my\rfloor\mu(d)=\sum_{d=1}^{\min(n,m)}\sum_{x=1}^{\lfloor\frac nd\rfloor}\sum_{y=1}^{\lfloor\frac md\rfloor}\lfloor\frac{\lfloor\frac nd\rfloor}x\rfloor\lfloor\frac{\lfloor\frac md\rfloor}y\rfloor\mu(d)=\sum_{d=1}^{\min(n,m)}\mu(d)\left(\sum_{x=1}^{\lfloor\frac nd\rfloor}\lfloor\frac{\lfloor\frac nd\rfloor}x\rfloor\right)\left(\sum_{y=1}^{\lfloor\frac md\rfloor}\lfloor\frac{\lfloor\frac md\rfloor}y\rfloor\right)\end{equation}
+设 $f(n)=\sum_{i=1}^n \lfloor\frac  ni\rfloor$，则
+\begin{equation}\text{Ans}=\sum_{d=1}^{\min(n,m)}\mu(d)f(\lfloor\frac nd\rfloor)f(\lfloor\frac md\rfloor)\end{equation}
+$O\left(n\sqrt n\right)$ 时间预处理出 $f$ 后可以 $O(\sqrt n)$ 处理每个询问。
+<hidden 查看代码>
+<code cpp>
+const int MAXP=5e4+5;
+bool vis[MAXP];
+int prime[MAXP],mu[MAXP],cnt,f[MAXP];
+void Mu(){
+	vis[1]=true,mu[1]=1;
+	_for(i,2,MAXP){
+		if(!vis[i])mu[i]=-1,prime[cnt++]=i;
+		for(int j=0;j<cnt&&i*prime[j]<MAXP;j++){
+			vis[i*prime[j]]=true;
+			if(i%prime[j])
+			mu[i*prime[j]]=-mu[i];
+			else{
+				mu[i*prime[j]]=0;
+				break;
+			}
+		}
+	}
+}
+int cal(int n){
+	int lef=1,rig=0,ans=0;
+	while(lef<=n){
+		rig=n/(n/lef);
+		ans+=(rig-lef+1)*(n/lef);
+		lef=rig+1;
+	}
+	return ans;
+}
+inline LL cal(int i,int n,int m){
+	int lef=1,rig=0;
+	LL ans=0;
+	while(lef<=i){
+		rig=min(n/(n/lef),m/(m/lef));
+		ans+=1LL*f[n/lef]*f[m/lef]*(mu[rig]-mu[lef-1]);
+		lef=rig+1;
+	}
+	return ans;
+}
+int main()
+{
+	Mu();
+	_for(i,2,MAXP)
+	mu[i]+=mu[i-1];
+	_for(i,1,MAXP)
+	f[i]=cal(i);
+	int t=read_int(),n,m;
+	while(t--){
+		n=read_int(),m=read_int();
+		enter(cal(min(n,m),n,m));
+	}
+	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

用户工具

站点工具

差别

页面工具