deco的gcd

思路：

数组用来存储所需要的素数(上界为个数中最大的一个，计为)，用线性筛即可。我们发现，求每两个数的的乘积我们可以把每个数质因数分解后单独考虑每个质因子的贡献。
考虑先用一个数组存下所有数出现的次数。然后将每个可能为个数的质因子的次方存下来(上界还是maxx，也就是代码中的f数组),里面存的是它是哪个质数的次方。然后我们从到去枚举一个，如果为，说明不是质因子的次方，因为我们只需要枚举质因子，所有此时直接掉，因为不会对答案产生任何贡献，然后用倍数法去看是当前的的倍数的数有多少个，若有个，说明我可以组合出(计为p)对有这个因子的二元组，此时对答案产生的新的贡献就是。这里可能有些难理解，举个例子，比如当前要枚举，之前的和都已经被统计过了，且都乘了，也就是乘了，所以当前的这个我们只需要乘一个即可。然后最后直接输出即可。注意一下 和即可(开始我全开了 只有分，飞了)。

这是我改进后的代码(自认为较之前的好理解许多，可以参考一下)：

#include<cstdio>
#include<algorithm>
#define maxn 1000007
#define mod 998244353
using namespace std;
int a[maxn],f[maxn],prime[maxn],cnt,n,maxx,ans=1;
bool vis[maxn];
inline int pls(int a, int b) {int m=a+b;return m<mod?m:m-mod;}
inline int dec(int a, int b) {int m=a-b;return m<0?m+mod:m;}
inline int mul(int a, int b) {return 1ll*a*b%mod;}
inline int fpow(int a, long long b) {
  int ans=1;
  for(;b;b>>=1,a=mul(a,a))
    if(b&1) ans=mul(ans,a);
  return ans;
}
inline void init() {                   //线性筛。
  vis[0]=vis[1]=1;
  for(int i=2;i<=maxx;++i) {
    if(!vis[i]) prime[++cnt]=i;
    for(int j=1;j<=cnt&&i*prime[j]<=maxx;++j) {
      vis[i*prime[j]]=1;
      if(i%prime[j]==0) break;
    }
  }
}
int main() {
  scanf("%d",&n);
  for(int i=1,x;i<=n;++i) {
    scanf("%d",&x);
    ++a[x],maxx=max(maxx,x);
  }
  init();
  for(int i=1;i<=cnt;++i) {
    long long j=prime[i];            //标记每个可能为n个数质因子的所有在给定范围的次幂。
    while(j<=maxx) {
      f[j]=prime[i];
      j*=prime[i];
      if(j>maxx) break;
    }
  }
  for(int i=1;i<=maxx;++i) {          //对每个质因子单独考虑统计答案即可。
    if(!f[i]) continue;
    int r=0;
    for(int j=i;j<=maxx;j+=i) r+=a[j];
    ans=mul(ans,fpow(f[i],1ll*r*(r-1)>>1));
  }
  return 0;
}