零、寫在前面

這是打卡的第十五天，其中最后一道題之前有寫過，今天再次進行一個優化，主要知識點在

《演算法零基礎100講》(第14講) 最小公倍數https://blog.csdn.net/WhereIsHeroFrom/article/details/121113291https://blog.csdn.net/WhereIsHeroFrom/article/details/121113291

一、主要知識點

1.二分快速冪

主要利用到的思想就是如下的樣子，非常便于理解，

#define ll long long
ll f(ll a, ll b, ll c) {
    if (b == 0)
        return 1 % c;           // (1)
    ll v = f(a*a % c, b/2, c);  // (2)
    if (b % 2)
        v = v * a % c;          // (3)
    return v;
}

2.二分快速冪的非遞回實作(補充知識點)

其實使用遞回肯定是可以的，但是，為了優化空間復雜度以及常數級別的時間復雜度，我們可以考慮這個非遞回實作，這兩個思想其實是一個從前往后，但是遞回回傳的時候是從1開始往回傳值，最終得到結果的，為了方便理解，我換了一種方式大家看一下這個影片加深一下理解，希望大家可以熟練尋用，

int kuaisumi(int a, int k){
    int ans = 1;
    a %= mod;
    while(k){
        if(k&1) ans = (ans*a)%mod;
        a = (a * a) % mod;
        k>>= 1;
    }
    return ans;
}

二、課后習題

50.Pow(x,n)

50. Pow(x, n)https://leetcode-cn.com/problems/powx-n/

求一個數字的n次方，但是不能直接硬算，會超時，

主要思想

其實就是用之前的二分快速冪的非遞回實作，只不過這里不需要取模，所以把取模干掉就好了，

但是，這題有個大坑，給的數字是int的邊界，在轉換成正數的時候會超出范圍，所以，我們需要使用unsigned int進行變數的轉換吸收，具體看代碼把，

double myPow(double x, int n){
    double y = 1;    //保存結果
    unsigned m;    //接受n的轉換結果
    if(n < 0){    //如果n<0 就把x變成1/x n變 -n 統一運算
        x = 1/x;
        m = -(unsigned int)n;
    }
    else m = n;
    while(m){            //非遞回二分快速冪
        if(m&1 == 1) y *= x;
        x *= x;
        m >>= 1;
    }
    return y;
}

結果分析

還是可以的，

其實遞回實作也可以 我放一個做參考

double f(double a,unsigned int n) {
    if (n == 0)
        return 1; 
    double v = f(a*a , n/2); 
    if (n % 2)
        v = v * a ; 
    return v;
}


double myPow(double x, int n){
    double y = 1;
    unsigned m;
    //if(x == 1) return y;
    if(n < 0){
        x = 1/x;
        m = -(unsigned int)n;
    }
    else m = n;
    y = f(x,m);
    return y;
}

372.超級次方

372. 超級次方https://leetcode-cn.com/problems/super-pow/

主要思想

主要問題其實是出現在資料的及時取余，我們這里用的是下面的遞推式，就很好做運算了，

int mod = 1337;

int kuaisumi(int a, int k){//快速冪的實作
    int ans = 1;
    a %= mod;
    while(k){
        if(k&1) ans = (ans*a)%mod;
        a = (a * a) % mod;
        k>>= 1;
    }
    return ans;
}

int superPow(int a, int* b, int bSize){
    if(!bSize) return 1;//如果沒資料回傳1
    int ans ;
    ans = kuaisumi(a,b[bSize - 1])*kuaisumi(superPow(a,b,bSize - 1),10);//遞回呼叫
    return ans%mod;
}

結果分析

湊合湊合，

1808.好因子的最大數目

1808. 好因子的最大數目https://leetcode-cn.com/problems/maximize-number-of-nice-divisors/

這個已經做過了，題解在，說真的，這個不看血虧，你能感受到數學的魅力是多么的強大

[解題報告]《演算法零基礎100講》(第10講) 因子分解和列舉(下)_XingleiGao的博客-CSDN博客零、寫在前面這是打卡的第十天，由于今天的第二題有一定的難度，需要我花費比較大的篇幅做題解，這是第二篇，主要講解第三題，我增加了一道題作為這道題的第一步輔助理解，上一篇在[解題報告]《演算法零基礎100講》(第10講) 因子分解和列舉(上)https://blog.csdn.net/qq_17593855/article/details/121052656一、預備知識?這部分不是特別難，只要你能理解，你就可以很容易的寫這道題整數拆分給定一個正整數n，...https://blog.csdn.net/qq_17593855/article/details/121053105但是，今天做個優化，就是把它優化成非遞回實作，代碼如下：

int mod = 1000000007;

long long kuaisumi(long long a, int k){
    long long ans = 1;
    while(k){
        if(k&1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        k >>= 1;
    }
    return ans;
}

int maxNiceDivisors(int primeFactors){
    if(primeFactors == 1) return 1;
    if(primeFactors % 3 == 0) return kuaisumi(3,primeFactors/3);
    else if(primeFactors % 3 == 1) return (kuaisumi(3,primeFactors / 3 - 1)*4)%mod;
    else return (kuaisumi(3,primeFactors/3)*2)%mod;
}

就很完美0.0

三、今日總結

看到今天打卡人數驟減，不知道是太難了還是怎樣，希望我的題解能給大家點思路，大家都要堅持下去呀