这个题好神呀。。Orz taorunz
有一个结论，这个结论感觉很优美：
$$ans = \prod_{i=1}^{n}\varphi(i)$$
至于为什么呢，大概是这样子的：
对于每个数字 $x$，第 $x$ 行有 $x - \varphi(x)$ 个数字不为 $1$，则说明这一行要被消 $x - \varphi(x)$ 次（别忘了每一行都会被 $1$ 给消一次），每次消元都会令 $A[x][x]$ 减一，所以 $A[x][x]$ 最后会变成 $\varphi(x)$，所以答案就是这个啦。
时间空间复杂度均为 $O(n)$。
#include <cstdio>
typedef long long LL;
#define N 1000000 + 5
#define M 100000 + 5
#define Mod 1000000007 int n, ans = , Phi[N], q[M]; int main()
{
scanf("%d", &n);
for (int i = ; i <= n; i ++)
{
if (!Phi[i])
{
Phi[i] = i - ;
q[++ q[]] = i;
}
for (int j = ; j <= q[] && i * q[j] <= n; j ++)
{
if (i % q[j] == )
{
Phi[i * q[j]] = Phi[i] * q[j];
break ;
}
Phi[i * q[j]] = Phi[i] * Phi[q[j]];
}
ans = (LL) ans * Phi[i] % Mod;
}
printf("%d\n", ans);
return ;
}
3288_Gromah