练习二、快速幂，素数筛

Hello_World

比赛链接：练习二、快速幂，素数筛

比赛说明

建议完成时间：1 月 16 日 00:00 ~ 1 月 17 日 23:59

学习资料：

1. G01 快速幂，推荐个好记的写法：

typedef long long LL;
const LL MOD = 1000000007;
LL fastPow(LL res, LL n) {
    LL ans;
    for (ans = 1; n != 0; n >>= 1) {
        if ((n & 1) == 1) {
            ans = ans * res % MOD;
        }
        res = res * res % MOD;
    }
    return ans;
}

1. 找素数的3种方法 试除法 埃氏筛 线性筛 动画演示过程 noi大纲数论基础

   2.1 在整型计算过程中尽量不要引入小数，也为了防止溢出，第二个视频中的 for (int i = 2; i <= sqrt(num); i++) 建议改成 for (int i = 2; i <= num / i; i++)

   2.2 视频中线性筛代码正确，但缩进不对，for 循环内第一个 if 与下面的 for 是平级关系，而不是 if 内有个 for 循环

   2.3 vector 相关可以后面再学，可以先用以下代码对照视频学习：

typedef long long LL;
const int maxn = 100000 + 100;
int cnt;
int prime[maxn];
bool isComposite[maxn];
void eulerSieve() {
    for(int i = 2; i <= n; ++i) {
        if(!isComposite[i]) {
            prime[cnt++] = i;
        }
        for(int j = 0; j < cnt && i <= n / prime[j]; ++j) {
            int k = i * prime[j];
            isComposite[k] = true;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
}

题目列表

A. 【模板】快速幂
B. [NOIP2013 提高组] 转圈游戏
C. [HNOI2008] 越狱
D. [ARC017A] 素数、コンテスト、素数
E. [USACO1.5] 回文质数 Prime Palindromes
F. 【模板】线性筛素数
G. 素数密度