数论题目小记

1.素数个数

【题目描述】求n到n+m内的素数个数

【解题报告】

“数论题目有时复杂度看着很大，实际上并没有那么大”

详见代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 3;
ll n, m, pr[N], tot, s[N];
bool vis[N];
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &n, &m);
        memset(vis, 0, sizeof vis);
        tot = m + 1;
        for (ll i = 2; i <= 1e6 && i <= n + m; i++)
            for (ll j = (n / i) * i; j <= n + m; j += i)  //保证跳到的都是合数
                if (j >= n && j != i && !vis[j - n]) {
                    vis[j - n] = 1; 
                    tot--;  //素数的个数等于总数-合数
                }
        printf("%lld
", tot);
    }
    return 0;
}

2.视野

【传送门】 http://oj.ipoweru.cn/problem/70014

【题目大意】给定正整数(C)，问从原点能看到几个坐标范围(0<x,y<=C)的整点。

【解题报告】

会被遮挡的是斜率相同的，也即(frac{y}{x})相同的坐标；而k作为分数可以约分，于是我们可以得到解决这道问题的思路：

求出(C * C) 矩阵中除((0,1),(1,0))以外所有互质点对
互质点对是对称存在的，欧拉函数求出的是互质的数，所以欧拉出来的结果要x2；对角线不需要x2因为它没有对称点对（它在对称轴上）

（刨除((0,1),(1,0))是题目要求，而下一道双倍经验题要求的范围不一样，要重新仔细思考范围嗷~）

到此，做法就呼之欲出了：欧拉函数求和。

#include <bits/stdc++.h>
const int N = 1e6 + 5;
#define int long long
using namespace std;
int t, c, n = 1e6, prime[N], phi[N], tot,ans;
bool vis[N];

void getprime() {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < tot && i * prime[j] <= n; ++j) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
        }
    }
}

signed main() {
    getprime();
    scanf("%lld",&t);
    while (t--) {
      ans = 0;
      scanf("%lld", &c);
      for (int i = 1; i <= c; i++)   ans += phi[i];
      ans = ans * 2 - 1;  //这是简写，其实应写成（ans - 1） * 2 + 1  (这是因为对角线只有一个，所以要-1
      printf("%lld
",ans);
    }
    return 0;
}

（双倍经验） SDOI 仪仗队

要注意的是，题目中体委站的位置是((1,1))，不是原点；当 (N = 1)时，需要特判(ans = 0)。

（从实际意义上来说，(N=1)即矩阵只有体委一个人，他当然不可能看到其他人；）

#include <bits/stdc++.h>
const int N = 1e6 + 5;
#define int long long
using namespace std;
int t, c, n = 1e6, prime[N], phi[N], tot,ans;
bool vis[N];

void getprime() {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < tot && i * prime[j] <= n; ++j) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
        }
    }
}

signed main() {
      getprime();
      std::cin >> c;
      if(c == 1) {
      	std::cout << "0";
      	return 0;
	  }
      for (int i = 1; i <= c - 1 ; i++)   ans += phi[i];
      ans = ans * 2 + 1;  
      std::cout << ans;
      return 0;
}