SGU102 Coprimes
知识准备
约定 对于一个整数n，小于n且和n互质的正整数（包括1）的个数，记作 dp(n)
性质一 对于素数p，有dp(p)=p-1
对于两个不同的素数p，q，它们的乘积n=p*q满足 dp(n)=dp(p)*dp(q)（证明略，中国剩余定理）
欧拉函数
任意一个整数n都可以表示成其素因子的乘积
n=(P1^K1)*(P2^K2)*..........*(Pi^Ki)
dp(n)=(P1^(K1-1))（P1－1）*(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的素因子就是2和3。这样在由变换的公式累乘就可以了。
#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 直接数
总结：对数学知识，像小学的质因数等遗忘了。甚为恐怖，虽然没学过数论，但这些常识的遗忘敲响了警钟。还有就是编码的能力太差，一些技巧需要不断的学习练习。这次做题也就是一个学习的过程，不求数量。数据结构的设计需要大量的经验，看来一时也别无他法。一个好的数据结构，可以让代码很简洁，算法效率很高。要知道算法是实施在数据结构之上的