杜教筛模板
又写了一遍，发现之前写的有错误，竟然水过去了，我线筛今天写错了两遍，我以后再写错我是傻逼。
#include<bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
typedef long long ll;
ll prime[N], cnt, mu[N], phi[N], sm[N], sp[N];
bool vis[N];
void init() {
mu[1] = phi[1] = 1;
for (int i = 2; i < N; i++) {
if (!vis[i])prime[++cnt] = i, mu[i] = -1, phi[i] = i - 1;
for (int j = 1; j <= cnt and prime[j] * i < N; j++) {
vis[prime[j] * i] = 1;
mu[prime[j] * i] = -mu[i];
phi[prime[j] * i] = (prime[j] - 1) * phi[i];
if (i % prime[j] == 0) {
mu[prime[j] * i] = 0;
phi[prime[j] * i] = phi[i] * prime[j];
break;
}
}
}
for (int i = 1; i < N; i++) sm[i] = sm[i - 1] + mu[i], sp[i] = sp[i - 1] + phi[i];
}
unordered_map<ll, ll>M, P;
ll m(ll n) {
if (n < N)return sm[n];
if (M.count(n)) return M[n];
ll ans = 1;
for (ll l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
ans -= (r - l + 1) * m(n / l);
}
return M[n] = ans;
}
ll p(ll n) {
if (n < N)return sp[n];
if (P.count(n)) return P[n];
ll ans = n * (n + 1) / 2;
for (ll l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
ans -= (r - l + 1) * p(n / l);
}
return P[n] = ans;
}
ll T, n;
int main() {
init();
scanf("%lld", &T);
while (T--) {
scanf("%lld", &n);
printf("%lld %lld
", p(n), m(n));
}
}
P1390 公约数的和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
[sum_{i=1}^nsum_{j = i + 1}^ngcd(i,j)
]
求解：
我们求 (t = sum_{i=1}^nsum_{j=1}^ngcd(i,j)=2sum_{i=1}^nsum_{j = i + 1}^ngcd(i,j) + sum_{i=1}^n)
[sum_{i=1}^nsum_{j=1}^ngcd(i,j)=sum_{i=1}^nsum_{j=1}^nsum_{d|gcd(i,j)}varphi(d)\=sum_{d=1}^nvarphi(d) lfloor dfrac ni
floorlfloor dfrac ni
floor
]
直接 (O(n)) 求就可以了，不需要分块，因为预处理就需要 (O(n)) 的时间差不了多少
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
ll phi[N], prime[N], cnt, vis[N];
ll sum[N];
void init(){
phi[1] = 1;
for(int i = 2; i < N;i++){
if (!vis[i])prime[++cnt] = i, phi[i] = i - 1;
for(int j = 1; j <= cnt and prime[j] * i < N;j++){
phi[prime[j] * i] = phi[i] * (prime[j] - 1);
vis[prime[j] * i] = 1;
if(i % prime[j] == 0){
phi[prime[j] * i] = phi[i] * prime[j];
break;
}
}
}
for (int i = 1;i < N;i++)sum[i] = sum[i - 1] + phi[i];
}
int main(){
init();
int n;scanf("%d", &n);
long long ans = 0;
for(int i = 1;i <= n;i++){
ans -= i;
ans += phi[i] * (n / i) * (n / i);
}
ans >>= 1;
printf("%lld
", ans);
}
还偷来了一个别人的筛素数的东西，但是跑的在 51nod 上跑的好像根 min25 差不了多少
#6235. 区间素数个数 - 题目 - LibreOJ (loj.ac)
P3912 素数个数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
min25
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 10;
int prime[maxn], cnt, vis[maxn];
int g[maxn], tot, w[maxn], idx1[maxn], idx2[maxn];
int sqr, n;
signed main() {
cin >> n;
sqr = sqrt(n + 0.5);
for (int i = 2; i <= sqr; i++) {
if (!vis[i]) {
prime[++cnt] = i;
}
for (int j = 1; j <= cnt && prime[j] * i <= sqr; j++) {
vis[prime[j]*i] = 1;
if (!i % prime[j])
break;
}
}
for (int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
w[++tot] = n / l;
g[tot] = w[tot] - 1;
if (w[tot] <= sqr)
idx1[w[tot]] = tot;
else
idx2[n / w[tot]] = tot;
}
for (int i = 1; i <= cnt; i++) {
for (int j = 1; j <= tot && prime[i] * prime[i] <= w[j]; j++) {
int k = (w[j] / prime[i] <= sqr) ? idx1[w[j] / prime[i]] : idx2[n / (w[j] / prime[i])];
g[j] = g[j] - (g[k] - i + 1);
}
}
cout << g[1] << endl;
}
别人的
暂时没懂
/*
* @Author: zhl
* @LastEditTime: 2020-11-27 10:24:11
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
int count(ll N) {
int v = sqrt(N);
vector<int> smalls(v + 1), larges(v + 1);
for (int i = 1; i <= v; ++i) smalls[i] = i - 1;
for (int i = 1; i <= v; ++i) larges[i] = N / i - 1;
for (int p = 2; p <= v; ++p) if (smalls[p] > smalls[p - 1]) {
int q = p * p, c = smalls[p - 1], e = min(v, N / q);
for (int i = 1; i <= e; ++i) {
larges[i] -= ((i * p <= v) ? larges[i * p] : smalls[N / (i * p)]) - c;
}
for (int i = v; i >= q; --i) smalls[i] -= smalls[i / p] - c;
}
return larges[1];
}
signed main(){
ll n;
cin >> n;
cout << count(n) << endl;
}
下面的是min25
这个代码是真的牛皮
偷过来的跑了第一
#include <cstdio>
#include <cassert>
#include <cmath>
#include <vector>
//Min_25
using namespace std;
using i64 = long long;
int isqrt(i64 n) {
return sqrtl(n);
}
i64 prime_pi(const i64 N) {
if (N <= 1) return 0;
if (N == 2) return 1;
const int v = isqrt(N);
int s = (v + 1) / 2;
vector<int> smalls(s); for (int i = 1; i < s; ++i) smalls[i] = i;
vector<int> roughs(s); for (int i = 0; i < s; ++i) roughs[i] = 2 * i + 1;
vector<i64> larges(s); for (int i = 0; i < s; ++i) larges[i] = (N / (2 * i + 1) - 1) / 2;
vector<bool> skip(v + 1);
const auto divide = [] (i64 n, i64 d) -> int { return double(n) / d; };
const auto half = [] (int n) -> int { return (n - 1) >> 1; };
int pc = 0;
for (int p = 3; p <= v; p += 2) if (!skip[p]) {
int q = p * p;
if (i64(q) * q > N) break;
skip[p] = true;
for (int i = q; i <= v; i += 2 * p) skip[i] = true;
int ns = 0;
for (int k = 0; k < s; ++k) {
int i = roughs[k];
if (skip[i]) continue;
i64 d = i64(i) * p;
larges[ns] = larges[k] - (d <= v ? larges[smalls[d >> 1] - pc] : smalls[half(divide(N, d))]) + pc;
roughs[ns++] = i;
}
s = ns;
for (int i = half(v), j = ((v / p) - 1) | 1; j >= p; j -= 2) {
int c = smalls[j >> 1] - pc;
for (int e = (j * p) >> 1; i >= e; --i) smalls[i] -= c;
}
++pc;
}
larges[0] += i64(s + 2 * (pc - 1)) * (s - 1) / 2;
for (int k = 1; k < s; ++k) larges[0] -= larges[k];
for (int l = 1; l < s; ++l) {
int q = roughs[l];
i64 M = N / q;
int e = smalls[half(M / q)] - pc;
if (e < l + 1) break;
i64 t = 0;
for (int k = l + 1; k <= e; ++k) t += smalls[half(divide(M, roughs[k]))];
larges[0] += t - i64(e - l) * (pc + l - 1);
}
return larges[0] + 1;
}
int main() {
i64 N;
while (~scanf("%lld", &N)) {
printf("%lld
", prime_pi(N));
}
}