題意：n個點的完全圖，邊權為lcm(i+1, j+1)，求mst，
題解：Min25篩
質數與2連，其他點與最小因子連，那么只要求n以內質數和即可，
比賽的時候本來想用區間篩打表的，這題其實套個Min25篩就好了，因為1e10，用int128存質數和，避免取模，結果調了一個下午，居然是n為1沒輸出，
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
#define pii pair<int, int>
using namespace std;
int t, mod;
ll n;
void print(__int128 x) {
if (!x) return;
if (x < 0) putchar('-'), x = -x;
print(x / 10);
putchar(x % 10 + '0');
}
const int N = 3400005;
int pt[N], pri[N >> 2], tot = 0;
ll sum[N];
inline void init() {
for (int i = 2; i <= N - 5; i++) {
sum[i] = sum[i - 1];
if (!pt[i]) pri[++tot] = i, sum[i] += i;
for (int j = 1; j <= tot && i * pri[j] <= N - 5; j++) {
pt[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
}
inline __int128 S(ll x) { return (__int128)x * (x + 1) / 2; }
int cnt, t1[N], t2[N];
ll last[N << 1];
__int128 h[N << 1];
inline __int128 calc(ll x) {
cnt = 0;
int id; ll l, r, t;
for (l = 1; l <= x; l = r + 1) {
t = (x / l); r = x / t; last[++cnt] = t; h[cnt] = S(t) - 1;
(t >= N - 5 ? t2[x / t] : t1[t]) = cnt;
}
for (int j = 1; j <= tot; j++) {
ll pw = (ll)pri[j] * pri[j];
if (pw > x) break;
for (int i = 1; i <= cnt && last[i] >= pw; i++) {
t = last[i] / pri[j], id = t >= N - 5 ? t2[x / t] : t1[t];
h[i] -= (__int128)pri[j] * (h[id] - sum[pri[j] - 1]);
}
}
return h[x >= N - 5 ? t2[1] : t1[x]];
}
int main() {
init();
scanf("%d", &t);
while (t--) {
scanf("%lld%d", &n, &mod);
++n;
if (n == 2) {
puts("0");
continue;
}
ll x = n + 3;
ll y = n - 3 + 1;
if ((n + 3) & 1) y /= 2;
else x /= 2;
__int128 ans = (x % mod) * (y % mod) % mod;
ans += calc(n) - 2;
ans %= mod;
print(ans);
puts("");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/117480.html
標籤：其他