首页 > itarticle > 赵队筛 && 线性筛gcd(i, n)

赵队筛 && 线性筛gcd(i, n)

admin 11月 23, 2020 0

Overview

赵队太神啦！虽然$(i,n)$可以筛是qls说的，不过既然这种筛法是赵队教我的，那就叫赵队筛好了！

Introduction

问题的提出：

请在线性时间内打出gcd(i, n)的表，其中n给定。

既然要求了线性时间，就不能用辗转相除法这种带log的做法了，因此想到利用gcd的积性用线性筛筛出来。

Editorial

利用$(i times j, n)=(i,n)times(j,n)[(i,j)=1]$筛。
更加形式化的，在线性筛的过程中，考虑$i * prime[j]$对应的答案，其实就是看$frac{n}{(i,n)}$能否整除$prime[j]$.

inline void (int n) {
    mark[1] = g[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!mark[i]) prime[++pnt] = i, g[i] = (n % i) ? 1 : i;
        for (int j = 1; j <= pnt && i * prime[j] <= n; ++j) {
            mark[i * prime[j]] = 1;
            g[i * prime[j]] = ((n / g[i]) % prime[j]) ? g[i] : g[i] * prime[j];
            if (i % prime[j] == 0) break;
        }
    }
}