Re: [閒聊] 每日leetcode

[sixB (6B)]

1922.

看到這個題號就想哈秋哈秋哈秋

練習power加速

還是數數兒

不過1e15很大要mod

直接開power會overflow

一個一個數會TLE

#

我記得好像可以shift就不用dpㄌ

不過我比較笨==

連dp都沒開 多做很多重複的事

#

原本用ee跟oo紀錄現在分別做了幾個

後來改直接一起5*4=20

using ll = long long;
class Solution {
public:
    int countGoodNumbers(long long n) {
        ll mod = 1e9 + 7;
        ll cnt = 1;
        bool even_end = n % 2;
        ll half = n / 2;
        while(half > 0){
            ll ee = 1, ect = 20;
            while(ee * 2 <= half){
                ee *= 2;
                ect = (ect * ect) % mod;
            }
            half -= ee;
            cnt = (cnt * ect) % mod;
        }
        if(even_end) cnt = (cnt * 5) % mod;
        return cnt;
    }
};


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1744563863.A.404.html