事实证明,$gcd$和$\sum$套起来真的比较好玩!

$gcd$和$∏$套起来……也很好玩。

下面的解法是莫比乌斯反演,运用这个解法,这道题的两个$∏$上面的数字可以不同(会有MLE的危险)。

事实证明我想多了,提交记录里有许多大佬用比我短还比我快的代码华丽AC了,然而我并看不懂,坐等其他解法的题解。

从莫比乌斯反演的角度来看,这题是道好题,解法很机智(至少在我这个蒟蒻看来是这样的。)

介绍莫比乌斯反演的文章

首先呢,题目叫我们求$\large{∏\limits_{i=1}^N∏\limits_{j=1}^N\dfrac{lcm(i,j)}{gcd(i,j)}}$,对大质数取模。

小学奥数告诉我们$lcm(i,j)=\dfrac{i*j}{gcd(i,j)}$

于是式子变成$\large{∏\limits_{i=1}^N∏\limits_{j=1}^N\dfrac{i*j}{gcd(i,j)^2}}$

再变成$\Large{\frac{∏\limits_{i=1}^N∏\limits_{j=1}^Ni*j}{\left(∏\limits_{i=1}^N∏\limits_{j=1}^Ngcd(i,j)\right)^2}}$

$∏\limits_{i=1}^N∏\limits_{j=1}^Ni*j$用一个很simple的快速幂就可以求出来了。

重点是如何求$∏\limits_{i=1}^N∏\limits_{j=1}^Ngcd(i,j)$

我们设$G(x,y)$为$\sum\limits_{i=1}^y\sum\limits_{j=1}^y[gcd(i,j)==x]$。

那么$\large{∏\limits_{i=1}^N∏\limits_{j=1}^Ngcd(i,j)=∏\limits_{i=1}^Ni^{G(i,N)}}$(好好理解哦)

这相当于把$gcd(i,j)$中相同的个数统计出来,然后用快速幂一次搞定。

考虑如何求出$G(1,N),G(2,N)……G(N,N)$。

一个暴力的做法是:直接套用这道题的解法,对每个$G(1,N)$用一个整除分块$O(\sqrt{n})$求,超时妥妥的。

讲一下这个做法。

我们要求$G(x,N)=\sum\limits_{i=1}^N\sum\limits_{j=1}^N[gcd(i,j)==x]$

我们把式子中所有的数整除x(这是老套路了)。

得到$G(x,N)=\sum\limits_{i=1}^{N/x}\sum\limits_{j=1}^{N/x}[gcd(i,j)==1]=G(1,N/x)$

也就是说我们只要能够求出求$G(1,N)$(N为变量)就好了。

接下来反演。

对一个确定的$N$设$f(x)=\sum\limits_{i=1}^N\sum\limits_{j=1}^N[gcd(i,j)==x]$ , $F(x)=\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}[x|gcd(i,j)]$

得出$F(N)=\sum\limits_{N|d}f(d)$

由反演定理得出$f(N)=\sum\limits_{N|d}\mu(d/N)F(d)$

先对$F(d)$进行简化,把式子中所有的数整除x。

得到$F(d)=\sum\limits_{i=1}^{N/x}\sum\limits_{j=1}^{N/x}[1|gcd(i,j)]=(N/x)^2$

我们要求$G(1,N)=f(1)$,直接令上式中$N=1$得到:

$f(1)=\sum\limits_d\mu(d)F(d)$

考虑到$F(d)=(N/x)^2$,在$1<=d<=N$时才有值(意义):

$f(1)=\sum\limits_{d=1}^{N}\mu(d)F(d)=\sum\limits_{d=1}^{N}\mu(d)(N/d)^2$

到这里已经可以$O(n)$求了,我们对$(N/d)$整除分块即可达到$O(\sqrt{n})$,这里不再赘述,感兴趣的同学可以阅读上面介绍莫反的文章。

接下来是正解,在上面的解法中稍作修改即可。

如果你会整除分块,再注意到$G(x,N)=G(1,N/x)$你会发现$N/x$的取值只会有$O(\sqrt{N})$种。

我们对$G(1,N/x)$整除分块,就只用求$O(\sqrt{N})$次$G(1,?)$复杂度从$O(N\sqrt{N})$降到$O(NlogN)$

(瓶颈在快速幂,如果有心思把分块进行到底,还可以变成$O(N)$)

#include<algorithm>
#include<cstdio>
#define mod 104857601
using namespace std;
int t,n,m,tn,p[200500],mu[1000500];
bool e[1000500];
long long sav[1000500],ans=1;
long long powM(long long a,long long t=mod-2)
{
  long long ans=1,buf=a;
  while(t){
  	if (t&1)ans=ans*buf%mod;
  	buf=buf*buf%mod;
  	t>>=1;
  }return ans;
}
void getmu()
{
  e[1]=1;mu[1]=1;
  for (int i=2;i<=1000100;i++){
  	if (!e[i]){
  	  p[++tn]=i;
  	  mu[i]=-1;
    }for (int j=1;j<=tn;j++){
      if (1ll*i*p[j]>1000100)break;
      e[i*p[j]]=1;
      mu[i*p[j]]=i%p[j] ? -mu[i] : 0;
      if (!i%p[j])break;
    }
  }//线筛出mu 
}
long long calc(int n)
{
  long long ans=0;
  int l=1,r;
  for (;l<=n;l=r+1){
  	r=n/(n/l);
  	ans+=1ll*(n/l)*(n/l)*(mu[r]-mu[l-1]);
  }return ans;
  //套路反演
}
int main()
{
  scanf("%d",&n);
  getmu();
  for (int i=2;i<=1000100;i++)mu[i]+=mu[i-1];
  //预处理mu前缀和
  for (int i=1;i<=n;i++){
  	int nn=n/i;
  	if (!sav[nn])sav[nn]=calc(nn);
    //如果求过就不用再求,懒人分块法
	ans=(ans*powM(i,sav[nn]))%mod;
  }ans=powM(ans);
  ans=(ans*ans)%mod;

  for (int i=1;i<=n;i++)
   ans=ans*powM(i,n*2)%mod;
  printf("%lld",ans);
  return 0;
}

所以这题可以出个加强版:求$\large{∏\limits_{i=1}^N∏\limits_{j=1}^M\dfrac{lcm(i,j)}{gcd(i,j)}},(N,M<=10^7)$。