程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Farey Sequence（歐拉函數）

Farey Sequence（歐拉函數）

編輯：關於C++

題意：給出式子F F中分子分母互質，且分子小於分母

例：

F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}
求解 fn的元素個數、

分析：本題就是求解歐拉函數值的前n項和，直接求解歐拉函數值的方法不行，因為用此法就是O（n^2)復雜度，采用遞推式求解是O(nlogn)復雜度

代碼如下：

#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
long long euler(long long  n){ //返回euler(n)
     long long  res=n,a=n;
     for(long long  i=2;i*i<=a;i++){
         if(a%i==0){
             res=res/i*(i-1);//先進行除法是為了防止中間數據的溢出
             while(a%i==0) a/=i;
         }
     }
     if(a>1) res=res/a*(a-1);
     return res;
}
//歐拉函數值直接求法，沒用上，超時
long long a[1000010];
int main(){
    for(long long i=1;i<=1000005;i++)a[i]=i;
    for(long long i=2;i<=1000005;i+=2)a[i]/=2;
    for(long long i=3;i<=1000005;i++)if(a[i]==i){
        for(long long j=i;j<=1000005;j+=i)
        a[j]=a[j]/i*(i-1);
    }//遞推公式  打表時很好用
    for(long long i=3;i<=1000005;i++){
        a[i]+=a[i-1];
    }
    long long n;
    while(scanf("%I64d",&n)!=EOF){
        if(n==0)break;
        printf("%I64d\n",a[n]);
    }
    return 0;
}

上一頁:hdu2588 GCD(歐拉函數)
下一頁:2016藍橋杯省賽題解

關於C++

LeetCode240:Search a 2D Matrix II

Write an efficient algorithm t

1、基本概念循環鏈表的定義：將單鏈表中最後一個數據元素的ne

UVA 1347(POJ 2677)Tour(雙調歐幾裡得旅行商問題)

TourTime Limit:3000MS Memory L

二叉樹的建立與遍歷（二）（c++實現）

【目標】建立如下所示的一棵二叉樹，並且輸出其對應的前序遍歷、

筆試題21 . LeetCode OJ (8)

class Solution {public: int my

leetcode筆記：Leetcode Letter Combinations of a Phone Number

一. 題目描述Given a digit string, r