SPOJ-Highways(HIGH)【行列式、Kirchhoff矩阵】

SPOJ-Count on a tree(COT)【主席树+LCA】

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

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

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

一看就不能暴力嘛。

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

结果惊呆了。

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

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

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

SPOJ-DETER
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32	`#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=s10+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[iprime[j]]=1;` `if(i%prime[j]==0){` `phi[iprime[j]]=phi[i]prime[j];` `break;` `}else` `phi[iprime[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;` `}`

相关文章

评论 (3)

1

[回复]

Avatar_small

foreseeable 说:
2013年10月14日 21:30

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

2

[回复]

Avatar_small

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

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

3

[回复]

Avatar_small

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

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