数论风骚套路汇总（不定期更新）

本文主要是介绍数论风骚套路汇总（不定期更新），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数论这个东西，确实值得深刻的研究。这里专门开一篇博客，记录遇见的一些奇技淫巧，一些妖艳的操作。（不定期更新）

---

10.30日更新(多项莫比乌斯反演)

求${\sum }_{i=1}^{a_1}{\sum }_{j=1}^{a_2}\dots \dots {\sum }_{x=1}^{a_x}gcd(i,j\dots \dots ,x)$其中循环的$\sum$最多有10个。

这道题看上去很不可做，但实际上跟BZOJ2005这道题的本质和推法是一样的。
设$min$是$a_1\dots \dots a_x$中的最小值

${\sum }_{i=1}^{a_1}{\sum }_{j=1}^{a_2}\dots \dots {\sum }_{x=1}^{a_x}gcd(i,j\dots \dots ,x)=={\sum }_{i=1}^{a_1}{\sum }_{j=1}^{a_2}\dots \dots {\sum }_{x=1}^{a_x}{\sum }_{k=1}^{min}k\ast [gcd(i,j\dots \dots ,x)=k]$

$={\sum }_{k=1}^{min}k\ast {\sum }_{i=1}^{\frac{a_1}{k}}{\sum }_{j=1}^{\frac{a_2}{k}}\dots \dots {\sum }_{x=1}^{\frac{a_x}{k}}[gcd(i,j\dots \dots ,x)=1]=={\sum }_{k=1}^{min}k\ast {\sum }_{i=1}^{\frac{a_1}{k}}{\sum }_{j=1}^{\frac{a_2}{k}}\dots \dots {\sum }_{x=1}^{\frac{a_x}{k}}{\sum }_{x|gcd(i,j\dots \dots ,x)}\mu (x)$

$={\sum }_{k=1}^{min}k\ast {\sum }_{x=1}^{\frac{min}{k}}\mu (x)[\frac{a_1}{kx}][\frac{a_2}{kx}]\dots \dots [\frac{a_x}{kx}]=={\sum }_{k=1}^{min}k\ast [\frac{a_1}{k}][\frac{a_2}{k}]\dots \dots [\frac{a_x}{k}]\phi (k)$

于是就可以开心的数论分块喽！

#include<bits/stdc++.h>
#define MAXN 1000005
#define inf 2147483647
#define ll long long
using namespace std;
const ll MD=1e9+7;
ll read(){char c;ll x;while(c=getchar(),c<'0'||c>'9');x=c-'0';while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}
ll T,n,i,s,top,l,r,Min,ans,a[15],vis[MAXN],pri[MAXN],phi[MAXN],sum[MAXN];
void pre(){vis[1]=1;phi[1]=1;sum[1]=1;for(ll i=2;i<=1000000;i++){if(!vis[i]) pri[++top]=i,phi[i]=i-1;for(ll j=1;j<=top&&i*pri[j]<=1000000;j++){vis[i*pri[j]]=1;if(i%pri[j]) phi[i*pri[j]]=phi[i]*phi[pri[j]]%MD;else{phi[i*pri[j]]=phi[i]*pri[j]%MD;break;}}sum[i]=sum[i-1]+phi[i];}
}
int main()
{T=read();pre();while(T--){n=read();l=1;ans=0;Min=2e9;for(ll i=1;i<=n;i++) a[i]=read(),Min=min(Min,a[i]);while(l<=Min){r=inf;s=1;for(ll i=1;i<=n;i++) {r=min(r,a[i]/(a[i]/l));s=(a[i]/l*s)%MD;}(ans+=(sum[r]-sum[l-1]+2*MD)%MD*s%MD)%MD;l=r+1;}printf("%lld\n",ans%MD);}return 0;
}

---

10.31日更新

设$f(x)={\sum }_{i=1}^{\infty }{\sum }_{j=1}^{\infty }[i\ast j|x]$，求${\sum }_{i=1}^{n}f(i)$

这道题的关键点就是转化，我们将条件转化，假设$\frac{x}{i\ast j}=k$，那么我们求$f(x)$只要枚举三元组$(i,j,k)$即可。

我们先假设$a\le b\le c$，那么我们$a$从$1$到$\sqrt[3]{n}$枚举，$b$从$a$到$\sqrt{\frac{x}{a}}$枚举，也就是for(ll a=1;a*a*a<=n;a++) for(ll b=a;a*b*b<=n;b++)，那

么$c$就可以取$[b,\frac{n}{a\ast b}]$，因为这样相乘都$\le n$。于是用方案乘以这三元组倒换顺序的方案数即可。

核心代码，可以证明复杂度是$O(n^{\frac{2}{3}})$，非常优秀。

for(ll a=1;a*a*a<=n;a++)    for(ll b=a;a*b*b<=n;b++){    ll c=n/(a*b);    if(c<b) break;   if(a==b)   ans+=(c-b)*3+1;  else   ans+=(c-b)*6+3; }

这篇关于数论风骚套路汇总（不定期更新）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---