CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:数论_3 [2020/07/10 09:57]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:数论_3 [2020/07/27 22:57] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:数论_3被移动至2020-2021:teams:legal_string:jxm2001:数论_3
@@ 行 19: / 行 19: @@
 移项得
-\begin{equation}g(1)S(n)=\sum_{i=1}^n (f\ast g)(i)-\sum_{d=2}^n g(d)S(\lfloor\frac nd\rfloor)\tag{1}\end{equation}
+\begin{equation}g(1)S(n)=\sum_{i=1}^n (f\ast g)(i)-\sum_{d=2}^n g(d)S(\lfloor\frac nd\rfloor)\end{equation}
 观察式子，发现如果能快速求出 $(f\ast g)(n)$ 和 $g(n)$ 的前缀和，就可以通过整数分块和记忆化搜索快速求出 $S(n)$。
@@ 行 74: / 行 74: @@
 == 题解 ==
-取 $f=\varphi,g=I$，则$(f\ast g)=id$，根据 $(1)$ 式，有
+取 $f=\varphi,g=I$，则$(f\ast g)=id$，根据杜教筛有
 \begin{equation}I(1)S(n)=\sum_{i=1}^n id(i)-\sum_{d=2}^n I(d)S(\lfloor\frac nd\rfloor)\end{equation}
@@ 行 82: / 行 82: @@
 \begin{equation}S(n)=\frac {n(n+1)}2-\sum_{d=2}^n S(\lfloor\frac nd\rfloor)\end{equation}
-取 $f=\mu,g=I$，则$(f\ast g)=e$，根据 $(1)$ 式，有
+取 $f=\mu,g=I$，则$(f\ast g)=e$，根据杜教筛有
 \begin{equation}I(1)S(n)=\sum_{i=1}^n e(i)-\sum_{d=2}^n I(d)S(\lfloor\frac nd\rfloor)\end{equation}
@@ 行 92: / 行 92: @@
 <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=5e6+5;
 bool vis[MAXP];
@@ 行 222: / 行 175: @@
 		enter(S_mu(n));
 	}
+    return 0;
+}
+</code>
+</hidden>
+=== 习题二 ===
+[[https://www.luogu.com.cn/problem/P3768|洛谷p3768]]
+== 题意 ==
+给定 $n,p$，计算
+\begin{equation}\sum_{i=1}^n\sum_{j=1}^n ij\text{gcd}(i,j)\bmod p\end{equation}
+== 题解 ==
+先把 $\text{gcd}$ 转化为莫比乌斯函数，有
+\begin{equation}\sum_{i=1}^n\sum_{j=1}^n ij\text{gcd}(i,j)=\sum_{d=1}^n d\sum_{i=1}^n\sum_{j=1}^nij[(i,j)==d]=\sum_{d=1}^n d^3\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}ij[(i,j)==1]=\sum_{d=1}^n d^3\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}ij\sum_{k\mid (i,j)}\mu(k)\end{equation}
+改变枚举顺序，有
+\begin{equation}\sum_{d=1}^n d^3\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}ij\sum_{k\mid (i,j)}\mu(k)=\sum_{d=1}^n d^3\sum_{k=1}^{\lfloor\frac nd\rfloor}\mu(k)\sum_{k\mid i}^{i\le\lfloor\frac nd\rfloor}i\sum_{k\mid j}^{j\le\lfloor\frac nd\rfloor}j=\sum_{d=1}^n d^3\sum_{k=1}^{\lfloor\frac nd\rfloor}k^2\mu(k)\left(\sum_{i=1}^{\lfloor\frac n{dk}\rfloor}i\right)^2\end{equation}
+设 $dk=T,S(n)=\sum_{i=1}^n i$，将 $k=\frac Td$ 代入，有
+\begin{equation}\sum_{d=1}^n d^3\sum_{k=1}^{\lfloor\frac nd\rfloor}k^2\mu(k)\left(\sum_{i=1}^{\lfloor\frac n{dk}\rfloor}i\right)^2=\sum_{T=1}^n S(\lfloor\frac nT\rfloor)T^2\sum_{d\mid T} d\mu\left(\frac Td\right)=\sum_{T=1}^n S(\lfloor\frac nT\rfloor)T^2\varphi(T)\end{equation}
+考虑数论分块 $+$ 杜教筛，设 $F(n)=\sum_{i=1}^nf(i),f(n)=n^2\varphi(n),g(n)=n^2$，有
+\begin{equation}(f\ast g)(n)=\sum_{d\mid n}f(d)g(\frac nd)=\sum_{d\mid n}d^2\varphi(d)\left(\frac nd\right)^2=n^2\sum_{d\mid n}\varphi(d)=n^3\end{equation}
+根据杜教筛公式，有
+\begin{equation}F(n)=\sum_{i=1}^n i^3-\sum_{d=2}^n d^2F\left(\lfloor\frac nd\rfloor\right)\end{equation}
+再根据 $\sum_{i=1}^n i^3=\left(\frac {n(n+1)}2\right)^2,\sum_{i=1}^n i^2=\frac {n(n+1)(2n+1)}6$，便可以快速计算出 $F(n)$。
+事实上，杜教筛在计算出 $F(n)$ 的同时也计算出了所有 $F\left(\lfloor\frac nd\rfloor\right)$ 的值。
+所以利用记忆化搜索，外层嵌套分块不影响时间复杂度，仍为 $O\left(n^{\frac 23}\right)$。
+<hidden 查看代码>
+<code cpp>
+int mod,inv2,inv6;
+int quick_pow(LL a,LL b,int mod){
+	LL t=1;
+	while(b){
+		if(b&1)
+		t=t*a%mod;
+		a=a*a%mod;
+		b>>=1;
+	}
+	return t%mod;
+}
+template <typename T1,typename T2>
+struct HASH_Table{
+	static const int HASH_MOD=3000017,MAXS=5e6;
+	struct cell{
+		T1 key;T2 val;
+		int next;
+	}e[MAXS];
+	int head[HASH_MOD],cnt;
+	void clear(){mem(head,0);cnt=0;}
+	T2 insert(T1 Key,T2 Value){
+		int h=Key%HASH_MOD;
+		e[++cnt].key=Key,e[cnt].val=Value,e[cnt].next=head[h];
+		head[h]=cnt;
+		return Value;
+	}
+	T2 find(T1 Key){
+		int h=Key%HASH_MOD;
+		for(int i=head[h];i;i=e[i].next){
+			if(e[i].key==Key)
+			return e[i].val;
+		}
+		return -1;
+	}
+};
+HASH_Table<LL,int> pre_2;
+const int MAXP=8e6;
+bool vis[MAXP];
+int prime[MAXP],pre_1[MAXP],cnt;
+void Pre(){
+	vis[1]=true,pre_1[1]=1;
+	_for(i,2,MAXP){
+		if(!vis[i])pre_1[i]=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])
+			pre_1[i*prime[j]]=pre_1[i]*(prime[j]-1);
+			else{
+				pre_1[i*prime[j]]=pre_1[i]*prime[j];
+				break;
+			}
+		}
+	}
+	_for(i,2,MAXP)
+	pre_1[i]=(1LL*i*i%mod*pre_1[i]+pre_1[i-1])%mod;
+}
+int Pow_1s(LL n){n%=mod;return n*(n+1)%mod*inv2%mod;}
+int Pow_2s(LL n){n%=mod;return n*(n+1)%mod*(2*n+1)%mod*inv6%mod;}
+int Pow_3s(LL n){n%=mod;LL t=n*(n+1)%mod*inv2%mod;return t*t%mod;}
+int S(LL n){
+	if(n<MAXP)
+	return pre_1[n];
+	if(pre_2.find(n)!=-1)
+	return pre_2.find(n);
+	LL ans=Pow_3s(n),lef=2,rig;
+	while(lef<=n){
+		rig=n/(n/lef);
+		ans=(ans-1LL*(Pow_2s(rig)-Pow_2s(lef-1))*S(n/lef))%mod;
+		lef=rig+1;
+	}
+	return pre_2.insert(n,ans);
+}
+int cal(LL n){
+	LL ans=0,lef=1,rig,t;
+	while(lef<=n){
+		rig=n/(n/lef);
+		t=Pow_1s(n/lef);t=t*t%mod;
+		ans=(ans+t*(S(rig)-S(lef-1)))%mod;
+		lef=rig+1;
+	}
+	return (ans+mod)%mod;
+}
+int main()
+{
+	mod=read_int();
+	inv2=quick_pow(2,mod-2,mod);
+	inv6=quick_pow(6,mod-2,mod);
+	Pre();
+	enter(cal(read_LL()));
     return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

页面工具