SGU102 Coprimes
知識(shí)準(zhǔn)備
約定 對(duì)于一個(gè)整數(shù)n，小于n且和n互質(zhì)的正整數(shù)（包括1）的個(gè)數(shù)，記作 dp(n)
性質(zhì)一 對(duì)于素?cái)?shù)p，有dp(p)=p-1
對(duì)于兩個(gè)不同的素?cái)?shù)p，q，它們的乘積n=p*q滿足 dp(n)=dp(p)*dp(q)（證明略，中國(guó)剩余定理）
歐拉函數(shù)
任意一個(gè)整數(shù)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)
簡(jiǎn)要分析
要設(shè)計(jì)程序，需要盡量減少變量的使用，可以使程序比較簡(jiǎn)單明了。那么就要對(duì)歐拉函數(shù)進(jìn)行一定的變換,對(duì)知識(shí)準(zhǔn)備的歐拉函數(shù)兩個(gè)公式進(jìn)行變換有
dp(n)=n*(1-1/p1)*(1-1/p2)*........*(1-1/pi)
代碼設(shè)計(jì)
要AC也可用笨辦法，直接求素?cái)?shù)，然后數(shù)一下就可以了
#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;
}
應(yīng)用歐拉函數(shù)是如何解決的呢，首先要知道素因數(shù)的求法，然后歐拉函數(shù)第一個(gè)公式，那么我們從素?cái)?shù)2開始，舉個(gè)例子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;
}
兩種做法對(duì)比一下
time memory
34ms 191kb 歐拉函數(shù)
71ms 171kb 直接數(shù)
總結(jié)：對(duì)數(shù)學(xué)知識(shí)，像小學(xué)的質(zhì)因數(shù)等遺忘了。甚為恐怖，雖然沒(méi)學(xué)過(guò)數(shù)論，但這些常識(shí)的遺忘敲響了警鐘。還有就是編碼的能力太差，一些技巧需要不斷的學(xué)習(xí)練習(xí)。這次做題也就是一個(gè)學(xué)習(xí)的過(guò)程，不求數(shù)量。數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)需要大量的經(jīng)驗(yàn)，看來(lái)一時(shí)也別無(wú)他法。一個(gè)好的數(shù)據(jù)結(jié)構(gòu)，可以讓代碼很簡(jiǎn)潔，算法效率很高。要知道算法是實(shí)施在數(shù)據(jù)結(jié)構(gòu)之上的