差别

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

--- 2020-2021:teams:legal_string:jxm2001:数论_1 [2020/07/02 20:05]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:数论_1 [2020/07/27 22:56] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:数论_1被移动至2020-2021:teams:legal_string:jxm2001:数论_1
@@ 行 39: / 行 39: @@
 ==== 算法简介 ====
-数论分块用于解决形如 $\sum_{i=1}^n \lfloor \frac ni\rfloor$ 的问题，时间复杂度 $O(\sqrt n)$。
+数论分块用于解决形如 $\sum_{i=1}^n a_if(\lfloor \frac ni\rfloor)$ 的问题，通过预处理 $a_i$ 前缀和，可以把时间复杂度降到  $O(\sqrt n)$。
 ==== 算法思想 ====
@@ 行 77: / 行 77: @@
 <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');}
 LL pre_s(int k){return 1LL*k*(k+1)/2;}
-LL cal(int n,int k){
+LL cal(int i,int n){
 	LL ans=0;
 	int lef=1,rig=0;
-	while(lef<=n){
+	while(lef<=i){
-		rig=min(n,k/(k/lef));
+		rig=min(i,n/(n/lef));
-		ans+=(pre_s(rig)-pre_s(lef-1))*(k/lef);
+		ans+=(pre_s(rig)-pre_s(lef-1))*(n/lef);
 		lef=rig+1;
 	}
@@ 行 126: / 行 92: @@
 	LL n=read_int(),k=read_int();
 	enter(n*k-cal(min(n,k),k));
+	return 0;
+}
+</code>
+</hidden>
+==== 算法练习 ====
+[[https://www.luogu.com.cn/problem/P2260|洛谷p2260]]
+=== 题意 ===
+求 \begin{equation}\sum_{i=1}^n\sum_{j=1}^m [i\ne j](n\ mod\ i)\ast (m\ mod\ j)\pmod {19940417}\end{equation}
+=== 题解 ===
+不妨设 $n\le m$。
+\begin{equation}\sum_{i=1}^n\sum_{j=1}^m [i\ne j](n\ mod\ i)\ast (m\ mod\ j)=\sum_{i=1}^n (n\ mod\ i)\ast\sum_{j=1}^m (m\ mod\ j)-\sum_{i=1}^n (n\ mod\ i)\ast (m\ mod\ i)\end{equation}
+前面两项解法同模板题，主要关注最后一项。
+\begin{equation}\sum_{i=1}^n (n\ mod\ i)\ast (m\ mod\ i)=\sum_{i=1}^n n\ast m-n\ast i\ast \lfloor\frac mi\rfloor-m\ast i\ast \lfloor\frac ni\rfloor+i^2\ast\lfloor\frac ni\rfloor\ast\lfloor \frac mi\rfloor\end{equation}
+类似的，也可以用数论分块解决，注意这条式子的最后一项需要同时处理 $n$ 和 $m$ 的分块边界。
+<hidden 查看代码>
+<code cpp>
+const int mod=19940417;
+LL inv6;
+LL exgcd(LL a,LL b,LL &tx,LL &ty){
+	if(b==0){
+		tx=1,ty=0;
+		return a;
+	}
+	LL re=exgcd(b,a%b,ty,tx);
+	ty-=a/b*tx;
+	return re;
+}
+LL pre_s_1(int k){return 1LL*k*(k+1)/2%mod;}
+LL s_1(int lef,int rig){return (pre_s_1(rig)-pre_s_1(lef-1))%mod;}
+LL pre_s_2(int k){return 1LL*k*(k+1)%mod*(2*k+1)%mod*inv6%mod;}
+LL s_2(int lef,int rig){return (pre_s_2(rig)-pre_s_2(lef-1))%mod;}
+LL cal_1(int i,int n){
+	LL ans=0;
+	int lef=1,rig=0;
+	while(lef<=i){
+		rig=min(i,n/(n/lef));
+		ans=(ans+s_1(lef,rig)*(n/lef)%mod)%mod;
+		lef=rig+1;
+	}
+	return ans;
+}
+LL cal_2(int i,int n,int m){
+	LL ans=0;
+	int lef=1,rig=0;
+	while(lef<=i){
+		rig=min(i,min(n/(n/lef),m/(m/lef)));
+		ans=(ans+s_2(lef,rig)*(n/lef)%mod*(m/lef)%mod)%mod;
+		lef=rig+1;
+	}
+	return ans;
+}
+int main()
+{
+	LL n=read_int(),m=read_int(),ans,t;
+	if(n>m)
+	swap(n,m);
+	exgcd(6,mod,inv6,t);
+	inv6%=mod;
+	ans=(n*n-cal_1(n,n))%mod*((m*m-cal_1(m,m))%mod)%mod;
+	ans=(ans-n*n%mod*m%mod)%mod;
+	ans=(ans+n*cal_1(n,m)%mod)%mod;
+	ans=(ans+m*cal_1(n,n)%mod)%mod;
+	ans=(ans-cal_2(n,n,m))%mod;
+	ans=(ans+mod)%mod;
+	enter(ans);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具