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 直接數
總結：對數學知識，像小學的質因數等遺忘了。甚為恐怖，雖然沒學過數論，但這些常識的遺忘敲響了警鐘。還有就是編碼的能力太差，一些技巧需要不斷的學習練習。這次做題也就是一個學習的過程，不求數量。數據結構的設計需要大量的經驗，看來一時也別無他法。一個好的數據結構，可以讓代碼很簡潔，算法效率很高。要知道算法是實施在數據結構之上的