自动搬运

查看原文

来自洛谷，原作者为

	command_block 众水皆昂首，饮月唯我一。

搬运于2025-08-24 21:40:45，当前版本为作者最后更新于2020-03-28 12:10:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意 : 给出$n$个数$a_{1...n}$,统计有多少个四元组满足$gcd(a_i,a_j,a_k,a_l)=1$

多组数据,$T\leq 100,n,a_i\leq 10^4$

• 类似的问题 : 给出若干个$[0,2^n)$内的数,对$m=[0,2^n)$求选取$k$元组and起来为$m$的方案数.

  开个桶记录出现次数,设为$F[n]$.

  先跑高维前缀和,然后$F[n]$就变成了“是$n$的超集的个数”

  我们令$F[n]=\dbinom{F[n]}{k}$,即“且起来是是$n$的超集的$k$元组个数”

  然后跑高维差分,即可得到“且起来是是$n$的$k$元组个数”。

  这道题告诉我们,对于按位取$\min/\max$的运算,其转移是个DAG,这类变换除了线性性之外往往还有其他优秀性质。

回到本题,其实gcd就是质因数向量上的$\min$.

先做一个约数前缀和,然后就变为了点值,每个点值变成$\dbinom{num}{4}$,然后跑一个约数差分即可。

这样甚至能得到$\gcd$为每个数的答案,我们最后只需取出$F[1]$即可。

容易发现,改成$k$元组同样能做。

复杂度可以用P5495 Dirichlet 前缀和做到$O(Tn\log\log n)$

代码很好写 :

#include<algorithm>
#include<cstdio>
#define MaxN 20050000
#define ll long long
using namespace std;
inline int read(){
  register int X=0;
  register char ch=0;
  while(ch<48||ch>57)ch=getchar();
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return X;
}
ll F[MaxN];
int p[MaxN/12],tn;
void solve()
{
  int m,n=1;
  if (scanf("%d",&m)==EOF)exit(0);
  for(int i=1,t;i<=m;i++){
    F[t=read()]++;
    n=max(n,t);
  }
  for(int i=1;p[i]<=n;i++)
    for(int j=n/p[i];j;j--)
      F[j]+=F[j*p[i]];
  for(int i=1;i<=n;i++)F[i]=(F[i]-3)*(F[i]-2)*(F[i]-1)*F[i]/24;
  for(int i=1;p[i]<=n;i++)
    for(int j=1;j*p[i]<=n;j++)
      F[j]-=F[j*p[i]];
  printf("%lld\n",F[1]);
  for(int i=1;i<=n;i++)F[i]=0;
}
bool e[MaxN];
int main()
{
  for(int i=2;i*i<=10000;i++)
    if (!e[i])
      for (int j=i*i;j<=10000;j+=i)
        e[j]=1;
  for(int i=2;i<=10000;i++)
    if (!e[i])p[++tn]=i;
  p[++tn]=10001;
  while(1)solve();
  return 0;
}

似乎利用$\mu$函数非零值较少写暴力也可以跑得很快……