【BZOJ3288】Mato矩阵 击表找规律

【BZOJ3288】Mato矩阵 打表找规律

首先行列式不多说了。

然后这道题可以用类似高斯消元的方法暴力搞到部分分。

但是正解是1~n求一遍欧拉函数，乘起来就是答案了。

这个怎么搞出来的呢？

考试的时候首先我们会打个暴力，然后排一下，然后发现，，，欧拉函数！

嗯。就是这样。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1001000
#define MOD 1000000007
using namespace std;

int n,prime[N],cnt;
long long phi[N];
bool vis[N];
void array()
{
	int i,j;
	phi[1]=1;
	for(i=2;i<=n;i++)
	{
		if(!vis[i])prime[++cnt]=i,phi[i]=i-1;
		for(j=1;prime[j]*i<=n;j++)
		{
			vis[prime[j]*i]=true;
			if(i%prime[j]==0)
			{
				phi[prime[j]*i]=phi[i]*prime[j];
				break;
			}
			phi[prime[j]*i]=phi[i]*(prime[j]-1);
		}
	}
}

int main()
{
	int i,j,k;
	long long ans=1;
	scanf("%d",&n);
	array();
	for(i=1;i<=n;i++)ans=ans*phi[i]%MOD;
	printf("%d\n",ans);
}