基础数学算法-可见的点

题目-可见的点

问题分析

对于任意一个点$(t\cdot x_0,t\cdot y_0)$, 斜率$k=\frac{y_0}{x_0}$, 当前点是可见的等价于$(x_0,y_0)$互质

欧拉函数$\varphi (i)$是$1\sim i$与$i$互质的数的个数, 可以提前统计出$\varphi (n)$, 然后加上坐标轴上的情况

算法步骤

在线性筛法质数过程中同步的统计欧拉函数, 算法时间复杂度$O(n)$, 将整个矩形一分为二, 分别累计$t=1\sim 1,1\sim 2,1\sim 3,...,1\sim n$的互质的数的个数(相当于半个矩形), 那么答案就等于$ans=2\times t-1+2$, $1$是$k=1$直线被多算了一次, $2$是坐标轴上的也要统计上

代码实现

如果每次都要调用$init$函数, 一定要对$st$数组和$cnt$清零, 否则会造成脏数据(上个用例的数据)的错误计算!!!

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int T, n;
int primes[N], cnt;
bool st[N];
int phi[N];

void init(int n) {
   
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
   
        if (!st[i]) {
   
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; ++j) {
   
            st[i * primes[j]] = true;
            if (i % primes[j]) {
   
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            }
            else {
   
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
        }
    }
}

void solve(int i) {
   
    memset(st, false, sizeof st);
    cnt = 0;
    cin >> n;
    init(n);

    int ans = 0;
    for (int i = 1; i <= n; ++i) ans += phi[i];
    ans = 2 * ans - 1 + 2;
    printf("%d %d %d\n", i, n, ans);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> T;
    for (int i = 1; i <= T; ++i) solve(i);

    return 0;
}

标准的不多次调用$init$的写法

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int T, n;
int primes[N], cnt;
bool st[N];
int phi[N];

void init(int n) {
   
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
   
        if (!st[i]) {
   
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; ++j) {
   
            st[i * primes[j]] = true;
            if (i % primes[j]) {
   
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            }
            else {
   
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
        }
    }
}

void solve(int i) {
   
    cin >> n;

    int ans = 0;
    for (int i = 1; i <= n; ++i) ans += phi[i];
    ans = 2 * ans - 1 + 2;
    printf("%d %d %d\n", i, n, ans);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    init(N - 1);
    cin >> T;
    for (int i = 1; i <= T; ++i) solve(i);

    return 0;
}