Graph Theory Class（min25筛求1e10素数前缀和）
Problem Description
This class is on graph theory. Mr. Kruskal teaches babies the concept of minimal spanning tree, and how to calculate the minimal spanning tree of a given graph.
Now, it's time for an in-class quizz. Mr. Kruskal shows a special graph G: G is a complete undirected graph with n vertices, and vertices in G are indexed from 1 to n. The weight of the edge between the ith vertex and the jth vertex is equal to lcm(i+1,j+1). Babies are asked to find the minimal spanning tree of G.
As a super baby, Baby Volcano quickly finds an answer, but he is not sure on the correctness of his answer. Your task is to tell Baby Volcano the weight sum of all edges on the minimal spanning tree, so that he could verify his answer.
Given two positive integers, lcm(i,j) is defined as the minimal positive integer k satisfying both i and j are factors of k.
Input
The first line contains a single integer t(1≤t≤50), the number of testcases.
For each testcase, the first line contains two integers n,K(1≤n≤1010,108≤K≤109).
The input guarantees that K is a prime number.
The input guarantees that there are no more than 5 testcases with n>109.
Output
For each testcase, output a single line with a single integer, the answer module K.
Sample Input
3 3 998244353 100 998244353 1000000000 998244353
Sample Output
10 6307 192026508
Source
调了3个半小时 还是凉了。。。不能说是板子问题，主要是我套前缀和公式前没对 n 取模，改了几次心态就炸了。
都是我的锅qaq（过了这题好像也莫得名额 博弈也没想出来
下面用了两个板子。
首先是来自知乎的：https://www.zhihu.com/question/29580448/answer/882461056
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1000010;
typedef long long ll;
ll mod;
ll qpow(ll a, ll b)
{
ll ans = 1;
while(b)
{
if(b & 1)
ans = ans * a % mod;
a = a * a % mod;
b /= 2;
}
return ans % mod;
}
ll prime[N], id1[N], id2[N], flag[N], ncnt, m;
ll g[N], sum[N], a[N], T, n;
inline ll ID(ll x)
{
return x <= T ? id1[x] : id2[n / x];
}
inline ll calc(ll x)
{
return x * (x + 1) / 2 - 1;
}
inline ll f(ll x)
{
return x;
}
inline void init()
{
ncnt = m = 0;
T = sqrt(n + 0.5);
for (ll i = 2; i <= T; i++)
{
if (!flag[i])
prime[++ncnt] = i, sum[ncnt] = sum[ncnt - 1] + i;
for (ll j = 1; j <= ncnt && i * prime[j] <= T; j++)
{
flag[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
for (ll l = 1; l <= n; l = n / (n / l) + 1)
{
a[++m] = n / l;
if (a[m] <= T)
id1[a[m]] = m;
else
id2[n / a[m]] = m;
g[m] = calc(a[m]);
}
for (ll i = 1; i <= ncnt; i++)
for (ll j = 1; j <= m && (ll)prime[i] * prime[i] <= a[j]; j++)
g[j] = g[j] - (ll)prime[i] * (g[ID(a[j] / prime[i])] - sum[i - 1]);
}
inline ll solve(ll x)
{
if (x <= 1)
return x;
return n = x, init(), g[ID(n)];
}
int main()
{
ll n, t;
scanf("%lld", &t);
while(t--) {
scanf("%lld%lld", &n, &mod);
ll ans = (solve(n + 1) - 2 + mod) % mod;
ll inv2 = qpow(2, mod - 2) % mod;
ll tmp = ((n + 4) % mod * (n - 1) % mod) % mod * inv2 % mod;
printf("%lld\n", (ans + tmp) % mod);
}
}下面来自https://www.cnblogs.com/purinliang/p/13703156.html
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod;
inline ll add_mod(ll x, ll y) {
return (x + y >= mod) ? (x + y - mod) : (x + y);
}
inline ll sub_mod(ll x, ll y) {
return (x < y) ? (x - y + mod) : (x - y);
}
inline ll mul_mod(ll x, ll y) { ///
return x * y % mod;
}
inline ll sum(ll n) {
n %= mod;
return (n * (n + 1)) / 2 % mod; ///
}
const int MAXN = 1e6 + 5;
ll ssum[MAXN];
ll lsum[MAXN];
bool mark[MAXN];
ll prime_cnt(ll n) {
const ll v = sqrt(n);
ssum[0] = 0;
lsum[0] = 0;
memset(mark, 0, sizeof(mark[0]) * (v + 1));
for(ll i = 1; i <= v; ++i) {
ssum[i] = sum(i) - 1;
lsum[i] = sum(n / i) - 1;
}
for(ll p = 2; p <= v; ++p) {
if(ssum[p] == ssum[p - 1])
continue;
ll psum = ssum[p - 1];
ll q = p * p;
ll ed = min((ll)v, n / q);
ll delta1 = (p & 1) + 1;
for(ll i = 1; i <= ed; i += delta1) {
if(!mark[i]) {
ll d = i * p;
ll tmp = (d <= v) ? lsum[d] : ssum[n / d];
tmp = sub_mod(tmp, psum);
tmp = mul_mod(tmp, p); ///
lsum[i] = sub_mod(lsum[i], tmp);
}
}
ll delta2 = p * delta1;
for(ll i = q; i <= ed; i += delta2)
mark[i] = 1;
for(ll i = v; i >= q; --i) {
ll tmp = ssum[i / p];
tmp = sub_mod(tmp, psum);
tmp = mul_mod(tmp, p); ///
ssum[i] = sub_mod(ssum[i], tmp);
}
}
return lsum[1];
}
ll qpow(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1)
ans = ans * a % mod;
a = a * a % mod;
b /= 2;
}
return ans % mod;
}
int main() {
ll n, t;
scanf("%lld", &t);
while(t--) {
scanf("%lld%lld", &n, &mod);
ll ans = prime_cnt(n + 1) - 2;
ll inv = qpow(2, mod - 2) % mod;
ll tmp = ((n + 4) % mod * (n - 1) % mod) * inv % mod;
printf("%lld\n", (ans + tmp) % mod);
}
return 0;
}
