BZOJ 3288 Mato矩阵 解题报告

这个题好神呀。。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

上一篇:9.19 考试总结


下一篇:区域医疗移动医疗影像解决方案2--基于FLEX的PACS