SPOJ3871 GCDEX
这题的描述对我这种语言能力残缺的人来说,复述起来太难:
3871. GCD Extreme
Problem code: GCDEX
Given the value of N, you will have to find the value of G. The meaning of G is given in the following code
G=0;
for(k=i;k< N;k++)
for(j=i+1;j<=N;j++)
{
G+=gcd(k,j);
}
/*Here gcd() is a function that finds the greatest common divisor of the two input numbers*/
Input
The input file contains at most 20000 lines of inputs. Each line contains an integer N (1Output for each line of input produce one line of output. This line contains the value of G for the corresponding N. The value of G will fit in a 64-bit signed integer.
实质上是求这么一个东西: G(n)=
求G(n)的话,可以先求T(n)=
,然后累加一下...额累加时第i项还要减个i~
,然后累加一下...额累加时第i项还要减个i~
如果学过数论,应该有印象,小于n的数里gcd(i,n)=d的i一共有
个~这意味着:
个~这意味着:
T(n)=
;
;现在证明,T(n)是一个积性函数
证明:
设 m , n 满足 (m,n)=1:
则:
由于(m,n)=1,故dn与dm互素,所有dn,dm的组合正好取遍mn的约数
到了这里,只需考虑n等于素数的幂时T(n)的值:
根据T(n)的定义,显然有:
有了这个性质,就有可以在O(n)时间内用这个 牛X的筛法 把表打出来,然后求和还是O(n),查询什么的显然O(1)咯lol...
代码:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define FF(i,b) for(i=0;i<(b);i++)
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ZERO(x) do{memset(x,0,sizeof(x));}while(0)
#define SWAP(a,b) do{int _tmp=a;a=b;b=_tmp;}while(0)
#define INFI 2000000000
#define INFF 1e100
#define maxn 1000000
typedef long long LL;
int p[maxn+1],ph[maxn+1],pk[maxn+1],T[maxn+1];
LL G[maxn+1];
void sevie()
{
memset(p,0,sizeof(p));
int i,j;
p[0]=ph[0]=0;ph[1]=1;T[1]=1;
for(i=2;i<=maxn;i++)
{
if(!p[i]){p[++p[0]]=i;ph[i]=i-1;pk[i]=i;T[i]=(i<<1)-1;}
for(j=1;p[j]<=maxn/i;j++)
{
p[p[j]*i]=1;
if(i%p[j]){
ph[i*p[j]]=ph[i]*p[j];
pk[i*p[j]]=p[j];
T[i*p[j]]=T[i]*T[p[j]];
}
else{
ph[i*p[j]]=ph[i]*p[j];
pk[i*p[j]]=pk[i]*p[j];
if(i==pk[i])T[i*p[j]]=p[j]*T[i]+ph[i*p[j]];
else T[i*p[j]]=T[i/pk[i]]*T[pk[i]*p[j]];
break;
}
}
}
G[0]=0;
for(i=1;i<=maxn;i++)G[i]=G[i-1]+T[i]-i;
}
int main ( int argc, char *argv[] )
{
sevie();
int n;
while(scanf("%d",&n)!=EOF)
{
if(!n)break;
printf("%lld\n",G[n]);
}
return EXIT_SUCCESS;
}
牛逼的线性时间筛法
这个牛B的筛法是在这里看到的
复杂度是线性的，扩展性超好～
自己YY了几个可以扩展的内容，权当模板～
#define N 1024
//niubee linear sevie method
int phi[N],//欧拉函数
p[N],//素数表
ld[N],//最小素因子
ldt[N],//最小素因子的次数
min_pk[N],//if p==ld[n],min_pk[n]=1+p+p^2+...+p^ldt[n];
sig[N],//约数和
nd[N];//因子数
//依赖性:min_pk<-sig;ldt<-nd;
void sevie()
{
memset(p,0,sizeof(p));
int i,j;
phi[0]=0;phi[1]=1;//phi
ld[0]=0;ld[1]=1;//ld
ldt[0]=0;ldt[1]=1;//ldt
min_pk[0]=0;min_pk[1]=1;//min_pk
sig[0]=0;sig[1]=1;//sig
nd[0]=0;nd[1]=1;//nd
for(i=2;i<=N;i++)
{
if(!p[i]){
p[++p[0]]=i;
phi[i]=i-1;
ld[i]=i;
ldt[i]=1;
min_pk[i]=i+1;
sig[i]=i+1;
nd[i]=2;
}
for(j=1;p[j]<=N/i;j++)
{
p[p[j]*i]=1;
ld[p[j]*i]=p[j];
if(i%p[j]){
phi[p[j]*i]=phi[p[j]]*phi[i];
ldt[p[j]*i]=1;
min_pk[p[j]*i]=p[j]+1;
sig[p[j]*i]=sig[i]*sig[p[j]];
nd[p[j]*i]=nd[p[j]]*nd[i];
}
else{
phi[p[j]*i]=phi[i]*p[j];
ldt[p[j]*i]=ldt[i]+1;
min_pk[p[j]*i]=p[j]*min_pk[i]+1;
sig[p[j]*i]=sig[i]/min_pk[i]*min_pk[p[j]*i];
nd[p[j]*i]=nd[i]/(ldt[i]+1)*(ldt[p[j]*i]+1);
break;
}
}
}
}