杂题选做 Vol.2

abc446_e Multiple-Free Sequences

Statement

在满足 $(x,y)$ 和 $0 \le x,y \le M-1$ 条件的整数对中，有多少对使得由以下递推关系定义的无限序列 $(s_1, s_2, \ldots)$ 中没有任何项是 $M$ 的倍数？

• $s_1 = x$
• $s_2 = y$
• $s_n = A s_{n-1} + B s_{n-2}\ (n \ge 3)$

Solution

找循环节。代码实现略难，另外虽然本题可以直接使用 map 通过，但 unorder_map 使用 pair<> 做 key 的时候需要自定义 Hash：

struct PairHash {
    size_t operator()(const pair<int,int>& p) const noexcept {
        return (static_cast<uint64_t>(p.first) << 32) ^ static_cast<uint32_t>(p.second);
    }
};

submission

abc445_e Many LCMs

Statement

Solution

思路没什么好说的，但是质因数分解时如果用试除法，时间复杂度是 $O(\sqrt{a})$ 的，无法通过本题。因为本题 $a \le 10^7$ 可以先预处理出每一个数的最小质因数 lpf[i] ，就可以优化到 $O(\log a)$。

void init(){
    for(int i=2;i<=M;i++)lpf[i]=i;
    for(int i=2;i<=M;i++){
        if(lpf[i]==i){
            primes.push_back(i);
        }
        for(auto p:primes){
            if(p*i>M||p>lpf[i])break;
            lpf[p*i]=p;
        }
    }
}

submission