数列分块
常与数列分块连用
向下取整括号一定要加对
int End=0,N=a/d,M=b/d;
if(N<M) swap(N,M);
for(int Start=1;Start<=M;Start=End+1)
{
End=min(N/(N/Start),M/(M/Start));//注意边界
ans+=(sum[End]-sum[Start-1])*(long long)(N/Start)*(M/Start);//注意括号
}
常见公式
\[\sum_{d|n}\mu(d)=[n=1] \]\[\sum_{d|n}\phi (d)=n \]\[若f(n)=\sum_{d|n}g(d),则有g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d}) \]例题
P3455 [POI2007] ZAP-Queries
最基础的一题
假设\(a<=b\)
单次询问\(O(\sqrt n)\)
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define ull unsigned long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
//#define int long long
#define pb push_back
// #pragma comment(linker, “/STACK:512000000,512000000”)
using namespace std;
const int N = 1e6+5;
ll mu[N],n,tot,pr[N],m,sum[N];bool is[N];
ll a,b,d;
void getMu(int n)
{
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!is[i])
{
pr[++tot]=i;
mu[i]=-1;
}
for(int j=1;j<=tot&&i*pr[j]<=n;j++)
{
is[i*pr[j]]=1;
if(i%pr[j]==0)
{
mu[i*pr[j]]=0;
break;
}
mu[i*pr[j]]=-mu[i];
}
}
for(int i=1;i<=n;i++)
{
// cout<<mu[i]<<" ";
sum[i]=sum[i-1]+mu[i];
}
}
int main()
{
speed();
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
int T;
cin>>T;
getMu(5e4);
while(T--)
{
cin>>a>>b>>d;
ll ans=0;
if(a>b)swap(a,b);
// int End=0,N=a/d,M=b/d;
// if(N<M) swap(N,M);
// for(int Start=1;Start<=M;Start=End+1)
// {
// End=min(N/(N/Start),M/(M/Start));
// ans+=(sum[End]-sum[Start-1])*(long long)(N/Start)*(M/Start);
// }
int l=1,r;a/=d;b/=d;
while(l<=a)
{
r=min(a/(a/l),b/(b/l));
ans+=1ll*(sum[r]-sum[l-1])*(long long)(a/l)*(b/l);
l=r+1;
}
cout<<ans<<endl;
}
return 0;
}
P2257 YY的GCD
同理
\[\large \sum_{k=1}^n\sum_{t=1}^{\lfloor { \frac{n}{k}}\rfloor}\mu(t)\lfloor {\frac{n}{kt}} \rfloor \lfloor {\frac{m}{kt}} \rfloor (k\in prime) \]这样还没完，会超时，我们设\(T=kt\),则
\[\large \sum_{T=1}^n\lfloor {\frac{n}{T}} \rfloor\lfloor {\frac{m}{T}} \rfloor \times \sum_{k|T}\mu(\frac{T}{k}) (k\in prime) \]我们发现这东西是可以预处理出来的(类似狄利克雷前缀和)
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define ull unsigned long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
//#define int long long
#define pb push_back
// #pragma comment(linker, “/STACK:512000000,512000000”)
using namespace std;
const int N = 1e7+5;
int mu[N],n,tot,pr[N],m,f[N],sum[N];bool is[N];
void getMu(int n)
{
mu[1]=1;
for(int i=2;i<=n;i++)
{
if(!is[i])
{
pr[++tot]=i;
mu[i]=-1;
}
for(int j=1;j<=tot&&i*pr[j]<=n;j++)
{
is[i*pr[j]]=1;
if(i%pr[j]==0)
{
mu[i*pr[j]]=0;
break;
}
mu[i*pr[j]]=-mu[i];
}
}
for(int i=1;i<=tot;i++)
{
for(int j=1;pr[i]*j<=n;j++)
{
f[pr[i]*j]+=mu[j];
}
}
for(int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+f[i];
}
}
int main()
{
speed();
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
int T;
cin>>T;
getMu(1e7);
// for(int i=1;i<=10;i++)cout<<mu[i]<<" ";
// cout<<endl;
while(T--)
{
cin>>n>>m;
if(n>m)swap(n,m);
ll ans=0;
int l=1,r;
while(l<=n)
{
r=min(n/(n/l),m/(m/l));
ans+=1ll*(sum[r]-sum[l-1])*(long long)(n/l)*(m/l);
l=r+1;
}
cout<<ans<<endl;
}
return 0;
}