$#C240926B. GCD(波)

标签（Label）

数学推理
欧拉函数
狄利克雷卷积
素数筛
gcd
动态规划
高维前缀和

前言（Front talk）

$\qquad$不是哥们你考一道题直接把四节数论知识全部用到了，我听的懂个鬼啊？

网址（Website）

题目详情 - GCD(波) - Super

题解 - GCD(波) - Super

题解（Solution）

$\qquad$这里给的题解是欧拉函数的做法。

$\qquad$令 $g[i][j]$ 表示第 $i$ 个序列中因子 $j$ 有 $g[i][j]$ 个，考虑如何更新 $g$ 数组。考虑从大到小枚举每一个质数，并从值域的最大值往下递推计算贡献，每次数的贡献都会被一直除直到除不尽当前枚举的质数，因此这种操作类似于枚举质因数来得出因数。（手跑一下就会发现很好理解了）

$\qquad$因数 $d$ 的方案个数就是 $(\Pi_{i=1}^{n}(g[i][d]+1))-1$ ，用这个方案数乘上 $\phi(d)$ 即可。

出题者题解

【算法分析】

直接求 $gcd=d$ 时的方案数并不好求，我们转而求 $gcd$ 是 $d$ 的倍数的方案数。最后再做一遍类似差分的操作即可。

那么我们只需要满足所有选的数都是 $d$ 的倍数即可。我们要对每一个数列求一个 $g(n)=\sum_{n|d} f(d)$，其中 $f(d)$ 是数 $d$ 在第 $i$ 个序列中出现的次数。
这个过程被称为狄利克雷前缀和，用定义求可以做到 $n \ln n$，可以获得 $90$ 分的高分，利用类似 $FMT$（快速莫比乌斯变换）的技巧，在每个素数的位置求一遍前缀和，可以做到 $n \ln \ln n$ 即可通过。

最后一步的差分也可以使用类似技巧优化到 $n \ln \ln n$。

代码（Code）

枚举质因子与dp递推

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define ull long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int A = 1000005;
const int N = 1000005;
const int M = 24;
bool ST;

struct Q{int x,y,z;}q[N];
int n,m,a[M][N],ans=0;

int pr[N],cnt,mx;
bitset<N> isnp;
void Get_prime(){
	For(i,2,mx){
		if(!isnp[i]) pr[++cnt] = i;
		for(int j = 1; j<=cnt && pr[j]*i<=mx;j++){
			isnp[pr[j]*i] = true;
			if(i % pr[j] == 0) break;
		}
	}
}

int c[M][N],f[N];
void Solve(){
	For(j,1,n) For(i,1,cnt)
		for(int k = mx/pr[i];k;k--)
			c[j][k] += c[j][k*pr[i]];
	Rof(i,mx,1){
		int res = 1;
		For(j,1,n) res = res*(ull)(c[j][i]+1)%mod;
		f[i] = (res-1+mod)%mod;
		for(int k=2;(ull)k*i<=mx;k++)
			f[i] = (f[i]-f[k*i]+mod)%mod;
	}
	ull ans = 0;
	For(i,1,mx) (ans+=(ull)f[i]*i%mod)%=mod;
	printf("%lld\n",ans); 
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	n=rd(),m=rd();int Tim = clock();
	For(i,1,n) For(j,1,m) 
		c[i][a[i][j]=rd()]++,mx = max(mx, a[i][j]);
	Get_prime(),Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}

欧拉函数做法

>#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define ull __int128
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int A = 1000005;
const int N = 1000005;
const int M = 24;
bool ST;

struct Q{int x,y,z;}q[N];
int n,m,a[M][N],ans=0;

int pr[N],phi[N],cnt,mx;
bitset<N> isnp;
void Get_prime(){
	phi[1] = 1;
	For(i,2,mx){
		if(!isnp[i]) pr[++cnt] = i, phi[i] = i-1;
		for(int j = 1; j<=cnt && pr[j]*i<=mx;j++){
			isnp[pr[j]*i] = true;
			if(i % pr[j] == 0){
				phi[i * pr[j]] = phi[i] * pr[j];
				break;
			}
			phi[i * pr[j]] = phi[i] * phi[pr[j]];
		}
	}
}

int c[M][N];
void Solve(){
	For(i,1,n) For(j,1,cnt)
		for(int k = mx/pr[j]*pr[j];k;k-=pr[j])
			c[i][k/pr[j]] += c[i][k];
	For(d,1,mx){
		int tmp = 1;
		For(i,1,n) tmp = tmp * (c[i][d] + 1ll) % mod;
		ans = (ans + (tmp-1ll)*phi[d]%mod)%mod;
	}cout<<ans<<'\n';
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	n=rd(),m=rd();int Tim = clock();
	For(i,1,n) For(j,1,m) 
		c[i][a[i][j]=rd()]++,mx = max(mx, a[i][j]);
	Get_prime(),Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}