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

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

构造一个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;
}
Avatar_small
foreseeable 说:
2013年10月14日 21:30

请google“SPOJ DETER1&2, GCD Determinant | wywcgs's blog”

Avatar_small
foreseeable 说:
2013年10月14日 21:31

@foreseeable: PS:这个博客需要一些手段才能进入……但是应该讲得比较详细……而且这题有推广……应该是spoj 的 DETER2

Avatar_small
younis 说:
2015年8月19日 23:56

您真是太厉害了。。这都可以找到解。。然而那个页面上面不是就有链接论文写了这个结论么。。google一下就找到了。。:http://www.emis.de/journals/AUSM/C1-1/MATH1-4.PDF


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter