SPOJ-Find The Determinant(DETER)【线性筛phi】

dzy posted @ 2013年8月17日 22:50 in SPOJ with tags SPOJ 行列式欧拉函数线性筛 , 3474 阅读

构造一个n×n的矩阵A。其中A[i][j]=gcd(i,j)。求A的行列式。n<=200w。

一看就不能暴力嘛。

暴力一下求了几个值放到OEIS上查。

结果惊呆了。

A001088

Product of totient function: a(n) = Product_{k=1..n} phi(k)

然后欧拉筛出phi。然后就行了。

（求大神告诉我这是为什么）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int flag[2000010],n,m,cnt=0;
long long prime[500000],phi[2000010],maxn=0,an[500010];
char buf[5000000],*o=buf,*pt=buf;
inline long long getint(){
    long long s=0; while(*pt<'0'||*pt>'9')pt++;
    while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; return s;
}inline void print(long long x){
    char str[12],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}*o++='\n';
}int main(){
	fread(buf,1,5000000,stdin);
	n=getint();	for(long long i=1;i<=n;i++)	an[i]=getint(),maxn=(an[i]>maxn)?an[i]:maxn; 
	memset(flag,0,sizeof(flag));
	for(int i=2;i<=maxn;i++){
		if(!flag[i])	prime[cnt++]=i,phi[i]=i-1;
		for(int j=0;j<cnt&&prime[j]*i<=maxn;j++){
			flag[i*prime[j]]=1;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}else	phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}phi[1]=1;
	for(int i=2;i<=maxn;i++)	phi[i]=phi[i-1]*phi[i]%1000003;
	for(int i=1;i<=n;i++)	print(phi[an[i]]);
	return fwrite(buf,1,o-buf,stdout),0;
}