SGU102 Coprimes

知识准备

约定 对于一个整数n,小于n且和n互质的正整数(包括1)的个数,记作 dp(n)


性质一 对于素数p,有dp(p)=p-1

对于两个不同的素数pq,它们的乘积n=p*q满足 dp(n)=dp(p)*dp(q)(证明略,中国剩余定理)


欧拉函数

任意一个整数n都可以表示成其素因子的乘积

n=(P1^K1)*(P2^K2)*..........*(Pi^Ki)
dp(n)=(P1^(K1-1))P11*(P2^(K2-1))P2-1*.........*(Pi^(Ki-1))(Pi-1)


 


简要分析

要设计程序,需要尽量减少变量的使用,可以使程序比较简单明了。那么就要对欧拉函数进行一定的变换,对知识准备的欧拉函数两个公式进行变换有

dp(n)=n*(1-1/p1)*(1-1/p2)*........*(1-1/pi)


代码设计

AC也可用笨办法,直接求素数,然后数一下就可以了

#include<iostream>

int gcd(int a,int b)

{

int r=0;

r
=a%b;

while(r)

{

a
=b;

b
=r;

r
=a%b;

}

return b;

}


int main()

{

int n;

int sum=0;

std::cin
>>n;

for(int i=1;i<=n;++i)

{

if(gcd(n,i)==1)++sum;

}

std::cout
<<sum;

//system("pause");

return 0;

}


应用欧拉函数是如何解决的呢,首先要知道素因数的求法,然后欧拉函数第一个公式,那么我们从素数2开始,举个例子18/2 9/3 ,3/3那么9的素因子就是23。这样在由变换的公式累乘就可以了。

#include<iostream>

#include
<math.h>

int prime(int n)

{

for(int i=2;i<=(int)sqrt(n);++i)

{

if(n%i==0)return 0;

}

return 1;

}


int main()

{

int n,flag,d=2;

double ans;

std::cin
>>n;

ans
=n;

if(prime(n)&&n!=1)ans=n-1;

else{

while(n!=1)

{

flag
=0;

while(n%d==0)

{

flag
=1;

n
=n/d;

}

if(flag)ans*=(double)(1-(double)1/(double)d);

do{

++d;

}
while(!prime(d));

}

}

std::cout
<<ans;

return 0;

}


两种做法对比一下

time memory

34ms 191kb 欧拉函数

71ms 171kb 直接数


总结:对数学知识,像小学的质因数等遗忘了。甚为恐怖,虽然没学过数论,但这些常识的遗忘敲响了警钟。还有就是编码的能力太差,一些技巧需要不断的学习练习。这次做题也就是一个学习的过程,不求数量。数据结构的设计需要大量的经验,看来一时也别无他法。一个好的数据结构,可以让代码很简洁,算法效率很高。要知道算法是实施在数据结构之上的