2021-04-24 09:57 已编辑菜鸡小学 C++

关注

题解-牛客练习赛81

鸽子出题人来发题解了。
首先很抱歉因为出题人都是初三党所以时间调来调去，题解所以发得也比较慢。
特别感谢内测的那几位验题人以及审题人提出的建议。

T1-小 Q 与异或

签到题，主要考察关于异或的这个性质 $a\bigoplus a=0$ 。

我看大多数的人代码都比官方的做法简洁了 100 倍，甚至还有直接随机卡过去的。

下面是做法：

首先肯定要按 $p$ 从小到大排序，这里有一个很坑的地方：如果同一个位置出现了不同的 $x$ 值，直接输出 $-1$ 。

如果当前位置离上一次的位置是偶数，就可以这样子构造：

for (int j = be + 1; j < i - 1; j++) ans[j] = s[be];
if (now == 0) {
    ans[i - 1] = (1ll << 30);
    ans[i] = (1ll << 30) ^ s[be];
}else {
    ans[i - 1] = (1ll << 30) ^ s[be];
    ans[i] = (1ll << 30) ^ now;
}

就直接把中间一段先赋值为上一次的异或前缀和，然后看这一次要的值是不是 $0$ ，如果是，那就直接把 $ans_i=t\bigoplus s_{last}$ ， $ans_{i-1}=t$ ， $t$ 是一个你喜欢的常数，这样子构造就可以消除掉 $s_{last}$ 的影响。

奇数的话有点麻烦：

for (int j = be + 1; j < i; j++) ans[j] = (1ll << 30);
if (now == 0 && s[be] == 0) {
   ans[be + 1] = (1ll << 30) ^ (998244353);
   ans[i] = 998244353;
} else
   ans[i] = (now ^ s[be]);

如果当前的值是零而且 $s_{last}=0$ ，那么你需要重新异或上一个常数，不然可能会构造出 $0$ ，导致答案错误。

std

#include <map>
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

#define int long long
#define LL long long

template <typename T>
inline void read(T &t) {
    t = 0;
    char c = getchar();
    int f = 1;
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -f;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        t = (t << 3) + (t << 1) + c - '0';
        c = getchar();
    }
    t *= f;
}
template <typename T, typename... Args>
inline void read(T &t, Args &... args) {
    read(t);
    read(args...);
}
template <typename T>
inline void write(T x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

void Min(int &a, int b) {
    if (a > b)
        a = b;
}
void Max(int &a, int b) {
    if (a < b)
        a = b;
};

int n, m, maxx, ans[1000005], s[1000005];
vector<int> G[1000005];

signed main() {
    read(n, m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        read(x, y);
        maxx = max(maxx, x);
        G[x].push_back(y);
    }
    int be = 0;
    for (int i = 1; i <= n; i++) {
        if (G[i].size()) {
            bool flag = 0;
            for (int j = 1; j < G[i].size(); j++) {
                int y = G[i][j];
                if (y != G[i][0]) {
                    flag = 1;
                    break;
                }
            }
            if (flag) {
                write(-1);
                return 0;
            }
            if (be == 0) {
                int now = G[i][0];
                if (i % 2 == 1) {
                    for (int j = 1; j < i; j++) ans[j] = (1 << 30);
                    if (now == 0) {
                        ans[1] = (1ll << 30) ^ (998244353);
                        ans[i] = 998244353;
                    } else
                        ans[i] = now;
                } else {
                    for (int j = 1; j < i - 1; j++) ans[j] = (1ll << 30);
                    ans[i - 1] = (1ll << 30);
                    ans[i] = (1ll << 30) ^ now;
                }
            } else {
                int now = G[i][0];
                if (be + 1 == i) {
                    if ((now ^ s[be]) == 0) {
                        write(-1);
                        return 0;
                    } else {
                        ans[i] = (now ^ s[i - 1]);
                    }
                } else {
                    if ((i - be) % 2 == 1) {
                        for (int j = be + 1; j < i; j++) ans[j] = (1ll << 30);
                        if (now == 0 && s[be] == 0) {
                            ans[be + 1] = (1ll << 30) ^ (998244353);
                            ans[i] = 998244353;
                        } else
                            ans[i] = (now ^ s[be]);
                    } else {
                        for (int j = be + 1; j < i - 1; j++) ans[j] = s[be];
                        if (now == 0) {
                            ans[i - 1] = (1ll << 30);
                            ans[i] = (1ll << 30) ^ s[be];
                        } else {
                            ans[i - 1] = (1ll << 30) ^ s[be];
                            ans[i] = (1ll << 30) ^ now;
                        }
                    }
                }
            }
            for (int j = be + 1; j <= i; j++) s[j] = s[j - 1] ^ ans[j];
            be = i;
        }
    }
    for (int i = maxx + 1; i <= n; i++) ans[i] = (LL)2e10;
    for (int i = 1; i <= n; i++)
        if (ans[i] == 0) {
            printf("-1");
            return 0;
        }
    for (int i = 1; i <= n; i++) write(ans[i]), printf(" ");
    return 0;
}

T2-小 Q 与彼岸花

这题为了比赛变得更加简单数据范围被削弱了，削弱后就是个简单题了，直接 $O(n^2)$ 区间 dp 就行。

说以下 $n\le 5\times 10^4$ 的做法，考虑分块，记 $b_{l,r}$ 表示第 $l$ 块到第 $r$ 块之间的答案，这个可以用 trie $O(n\sqrt{n}\log S)$ 搞出来， $S$ 是值域。

然后查询的话就上一个可持久化 trie，然后查边角就行。

std

#include <bits/stdc++.h>
using namespace std;
#define Int int
#define MAXN 100005
#define num bel[n]

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,m,cur,rt[MAXN],val[MAXN],bel[MAXN];
int ch[MAXN * 32][2],cnt[MAXN * 32],Ans[705][705];

int sta[705],fin[705];

void Insert (int a,int b,int t,int x){
	if (t < 0) return ;
	int i = (x >> t) & 1;
	ch[a][i] = ++ cur;
	ch[a][i ^ 1] = ch[b][i ^ 1];
	cnt[ch[a][i]] = cnt[ch[b][i]] + 1;
	Insert (ch[a][i],ch[b][i],t - 1,x);
}

int query (int a,int b,int t,int x){
	if (t < 0) return 0;
	int i = (x >> t) & 1;
	if (cnt[ch[a][i ^ 1]] > cnt[ch[b][i ^ 1]]) return (1 << t) + query (ch[a][i ^ 1],ch[b][i ^ 1],t - 1,x);
	else return query (ch[a][i],ch[b][i],t - 1,x);
}

signed main(){
	read (n,m);
	int siz = sqrt (n);
	memset (sta,0x7f,sizeof (sta));
	for (Int i = 1;i <= n;++ i) read (val[i]),bel[i] = (i - 1) / siz + 1;
	for (Int i = 1;i <= n;++ i) sta[bel[i]] = min (sta[bel[i]],i),fin[bel[i]] = i;
	for (Int i = 1;i <= n;++ i) rt[i] = ++ cur,Insert (rt[i],rt[i - 1],17,val[i]);
	for (Int i = 1;i <= num;++ i){
		int start = sta[i];
		for (Int j = i;j <= num;++ j){
			Ans[i][j] = Ans[i][j - 1];
			for (Int k = sta[j];k <= fin[j];++ k)
				Ans[i][j] = max (Ans[i][j],query (rt[k],rt[start - 1],17,val[k]));
		}
	}
	while (m --){
		int l,r;
		read (l,r);
		if (bel[r] - bel[l] <= 2){
			int ans = 0;
			for (Int i = l;i < r;++ i)
				ans = max (ans,query (rt[r],rt[i],17,val[i]));
			write (ans),putchar ('\n');
		}
		else{
			int bl = bel[l] + 1,br = bel[r] - 1;
			int ans = Ans[bl][br];
			for (Int i = l;i < sta[bl];++ i) ans = max (ans,query (rt[r],rt[l - 1],17,val[i]));
			for (Int i = fin[br] + 1;i <= r;++ i) ans = max (ans,query (rt[i],rt[l - 1],17,val[i]));
			write (ans),putchar ('\n');
		}
	}
	return 0;
}

T3-小 Q 与构造

$n \leq 300$

可以很简单的将整个序列拆成若干条链（如果你高兴也可以说若干个序列），使得这些链互不影响。设有 x 条链，第 i 条链的答案是 $q_i$ ，每条链互不影响，所以根据乘法原理，答案就是：

$\displaystyle \prod_{i=1}^x q_i$

有了这样的一个大概思路，接下来有几个问题有待解决：

- 如何将其拆成几个互不影响的链？
- 如何计算每条链的答案？

考虑对这个限制的性质入手。

x=ky 或者 $x=k^py$ 都是不能满足的。做题多的同学不难想到构造一条链（或者说序列？），设其首项为 a，满足：

$a,ak,ak^2,ak^3,\cdots , ak^s$

对于每一个之前没有用过的 $a$ 都做一个这样的序列，计算它们的答案就行了。

这样，拆出来的每一条链都是互相不影响的。我觉得很显然吧。

考虑计算答案，发现对于一条链来说，两个限制就相当于：

- 不能选择相邻的两个数（就是距离为 $1$ ）；
- 不能选择距离为 $p$ 的两个数。

再回看 $p \leq 10$ ，显然状压解决。

看实现情况， $O\left(\dfrac{n 2^p \log_k n}{k}\right)$ 。其实本意是用来乱搞的。

$n \leq 5 \times 10^6$

往里面随便走下性质。

- 性质 1：如果一个数能作为一条链（序列）的首项，那么这个数一定不是 k 的倍数。
随便猜都猜得到吧。

- 性质 2：当两个不同的首项 $a,b$ ，构造出来的序列长度是相等的，那么这个两个首项的链的贡献是一样的。
因为限制是相同的嘛。

所以可以只做一遍 dp，然后循环枚一遍就完了，时间复杂度 $O\left({n + 2^p \log_k n}\right)$ 。

$n \leq 10^{14}$

$n$ 有点大。

综合上面推出来的两个性质，加上一点简单的数论分块的知识，我们可以改写答案。

设 $c_x$ 为作为首项（注意，这里不包含不能作为首项的数）构造出来的序列长度为 $x$ 的数的数量， $sum_x$ 为构造出的序列长度为 $x$ 的贡献是多少。答案就是：

$\prod_{i=1}^{up}sum_x^{c_x}$

$sum_x$ 早就算出来了，考虑这个 $c_x$ 怎么算。

用一点简单的数论分块的知识，推出一段区间，使得里面的每一个数构造出来的序列长度为 x 不就得了（实际操作就是除法）。然后挪动区间就直接 $l=r+1$ 就完了。

注意要将算出来的区间中，排除掉能够整除 $k$ 的数。

代码不长。注意 $k=1$ 的特判。

T4-小 Q 与树

简单题，想怎么做就怎么做，可以淀粉质，可以树上启发式合并，甚至可以上权值线段树合并。

std 写的是树上启发式合并套平衡树，也没什么好讲的，合并的时候统计一下贡献就行。

#include <ctime>
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define Int int
#define MAXN 200005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

#define mod 998244353
int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}

vector <int> G[MAXN];
int n,ans,rt[MAXN],val[MAXN],dep[MAXN];
struct fhq_Treap{
	int son[MAXN][2],key[MAXN],siz[MAXN],sum1[MAXN],sum2[MAXN],sum3[MAXN];
#define ls(x) son[x][0]
#define rs(x) son[x][1]
	void Pushup (int x){
		siz[x] = siz[ls(x)] + siz[rs(x)] + 1,
		sum1[x] = add (sum1[ls(x)],add (sum1[rs(x)],val[x]));
		sum3[x] = add (sum3[ls(x)],add (sum3[rs(x)],dep[x]));
		sum2[x] = add (sum2[ls(x)],add (sum2[rs(x)],mul (val[x],dep[x])));
	}
	void Split (int u,int k,int &x,int &y){
		if (!u) return x = y = 0,void ();
		if (val[u] <= k) x = u,Split (rs(u),k,rs(u),y);
		else y = u,Split (ls(u),k,x,ls(u));
		Pushup (u);  
	}
	int Merge (int x,int y){
		if (!x || !y) return x + y;
		if (key[x] < key[y]) return rs(x) = Merge (rs(x),y),Pushup (x),x;
		else return ls(y) = Merge (x,ls(y)),Pushup (y),y;
	}
	void clear (int u){son[u][0] = son[u][1] = 0,key[u] = rand(),Pushup (u);}
	void insert (int &root,int u){
		int x,y;Split (root,val[u],x,y);
		root = Merge (x,Merge (u,y));
	}
	void count (int u,int du,int root){
		int x,y;Split (root,val[u],x,y);
		int res1 = add (sum2[x],mul (dec (dep[u],2 * du),sum1[x]));
		int res2 = add (mul (val[u],sum3[y]),mul (siz[y],mul (val[u],dec (dep[u],2 * du))));
		ans = add (ans,add (res1,res2)),Merge (x,y);
	}
	void ergodic (int u,int now,int &ano,bool flg){
		if (!now) return ;
		ergodic (u,ls(now),ano,flg),ergodic (u,rs(now),ano,flg);
		if (flg == 0) count (now,dep[u],ano);
		if (flg == 1) clear (now),insert (ano,now);
	}
}Tree;

void dfs (int u,int fa){
	dep[u] = dep[fa] + 1;
	for (Int v : G[u]) if (v ^ fa) dfs (v,u);
}

void dfs1 (int u,int fa){
	for (Int v : G[u]) if (v ^ fa) dfs1 (v,u);
	Tree.insert (rt[u],u);
	for (Int v : G[u]) if (v ^ fa){
		if (Tree.siz[rt[v]] > Tree.siz[rt[u]]) swap (rt[u],rt[v]);
		Tree.ergodic (u,rt[v],rt[u],0),Tree.ergodic (u,rt[v],rt[u],1);	
	}
}

signed main(){
    srand(time(0));
	read (n);
	for (Int i = 1;i <= n;++ i) read (val[i]),Tree.key[i] = rand();
	for (Int i = 2,u,v;i <= n;++ i) read (u,v),G[u].push_back (v),G[v].push_back (u); 
	dfs (1,0);for (Int i = 1;i <= n;++ i) Tree.Pushup (i);dfs1 (1,0),write (mul(ans,2)),putchar ('\n');
	return 0;
}

T5-小 Q 与函数求和 1

简单莫比乌斯反演题。

先不考虑 $k=-1$ 的时候。

$k\ge0$

$\sum_{i=1}^n\sum_{j=1}^n \varphi(\gcd(i,j)^kij)$

$\sum_{d=1}^n \sum_{i=1}^n\sum_{j=1}^n\varphi(d^kij) [\gcd(i,j)=d]$

$\sum_{d=1}^n \sum_{i=1}^{n/d} \sum_{j=1}^{n/d} \varphi(ijd^{k+2})[\gcd(i,j)=1]$

当 $k\ge 2$ 时。
$\varphi(ijd^{k})[\gcd(i,j)=1]=\dfrac{\varphi(ijd^{k-1})\varphi(d)d}{\varphi(d)}[\gcd(i,j)=1]=d\varphi(ijd^{k-1})[\gcd(i,j)=1]$

$\sum_{d=1}^n d^k\sum_{i=1}^{n/d} \sum_{j=1}^{n/d} \varphi(ijd^2)[\gcd(i,j)=1]$

$\sum_{d=1}^n d^k\sum_{i=1}^{n/d} \sum_{j=1}^{n/d} \dfrac{\varphi(id)\varphi(jd)d}{\varphi(d)}[\gcd(i,j)=1]$

$\sum_{d=1}^n \dfrac{d^{k+1}}{\varphi(d)}\sum_{i=1}^{n/d} \sum_{j=1}^{n/d} \varphi(id)\varphi(jd)[\gcd(i,j)=1]$

$\sum_{d=1}^n \dfrac{d^{k+1}}{\varphi(d)}\sum_{D=1}^{\frac{n}{d}}\mu(D)\sum_{i=1}^{n/dD} \sum_{j=1}^{n/dD} \varphi(idD)\varphi(jdD)$

$\sum_{T=1}^n \sum_{d|T}\dfrac{d^{k+1}}{\varphi(d)}\mu(\dfrac{T}{d})(\sum_{i=1}^{\frac{n}{T}}\varphi(iT))^2$

$k=-1$

$\sum_{d=1}^n\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}} \dfrac{\varphi(ijd^2)}{d}[\gcd(i,j)=1]$

$\sum_{d=1}^n\dfrac{1}{d}\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}} \varphi(ijd^2)[\gcd(i,j)=1]$
$\sum_{d=1}^n \dfrac{1}{d\varphi(d)}\sum_{D=1}^{\frac{n}{d}}\mu(D)\sum_{i=1}^{n/dD} \sum_{j=1}^{n/dD} \varphi(idD)\varphi(jdD)$
$\sum_{i=1}^n \sum_{d|T}\dfrac{\mu(\frac{T}{d})}{d\varphi(d)}(\sum_{i=1}^{n/T}\varphi(iT))^2$

然后就可以 $O(n\log n)$ 解决了。

T6-小 Q 与函数求和 2

结论与板子题。

$f(n,m)$ 这么 ex，肯定是有结论的，先给结论。
$f(n,m)=\sum_{m|i}^n \sigma_0(i)$
然后这里有两种证明过程，可以逆推和正推，先看逆推（需要你猜出结论）。
$\sum_{m|i}^n \sigma_0(i)=\sum_{m|i}^n \sum_{d|i}1=\sum_{d=1}^n\sum_{m|i}[d|i]=\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{m}\rfloor}[d|im]=\sum_{d=1}^n \lfloor\dfrac{n}{\operatorname{lcm}(d,m)}\rfloor$
正推的话是一样的，考虑一下这个 $\sum_{d=1}^n \lfloor\dfrac{n}{\operatorname{lcm}(d,m)}\rfloor$ 实际含义，对于每一个 $d$ 都相当于在求在 $n$ 以内有多少个数是 $m$ 的倍数且是 $d$ 的倍数。

然后带入原式子。
$\sum_{i=1}^n \sum_{j=1}^n \sum_{j|k}^i \sigma_0(k)$

$\sum_{k=1}^n \sigma_0(k)(n-k+1)\sum_{j=1}^n [j|k]$

后面这个不就是枚举的约数个数吗？

$\sum_{k=1}^n \sigma_0(k)^2(n-k+1)$

然后这东西怎么算，把式子拆成两部分，就是要求 $f(k)=\sigma_0(k)^2$ ， $g(k)=\sigma_0(k)^2k$ 的前缀和，考虑 min_25 筛。

算一下质数下的取值。
$f(p^k)=\sigma_0(p^k)^2=(k+1)^2$ ， $g(p^k)=\sigma_0(p^k)^2p^k=(k+1)^2p^k$ ，套进 min_25 筛的板子即可。时间复杂度 $\mathcal{O}(\dfrac{n^{\frac{3}{4}}}{\log n})$ ，如果用 min_26 筛，可以做到 $\mathcal{O}(n^{\frac{2}{3}})$ ，但是没有必要。

std:

#include <cstdio>
#include <map>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
#define LL long long
const int mod = 998244353;
int dec(int x, int y) { return x >= y ? x - y : x + mod - y; }
int mul(int x, int y) { return 1ll * x * y % mod; }
int add(int x, int y) {
    if (x + y >= mod)
        return x + y - mod;
    return x + y;
}
LL qkpow(LL x, LL power, LL mod) {
    x %= mod;
    LL ans = 1;
    for (; power; power >>= 1, (x *= x) %= mod)
        if (power & 1)
            (ans *= x) %= mod;
    return ans;
}
int sq, size, cnt;
int prime[1000005], id1[1000005], id2[1000005];
LL n, num[1000005], g[1000005], gprime[1000005];
bool vis[1000005];

LL S1(LL x, LL y) {
    if (prime[y] >= x)
        return 0;
    int p = (x <= sq ? id1[x] : id2[n / x]);
    int ans = dec(g[p], mul(4, y));
    for (int i = y + 1; i <= cnt && 1ll * prime[i] * prime[i] <= x; i++) {
        LL pkx = prime[i];
        for (int k = 1; pkx <= x; k++, pkx *= prime[i]) {
            LL pkxm = pkx % mod;
            ans = add(ans, mul(add(k, 1), mul(add(k, 1), S1(x / pkx, i) + (k > 1))));
        }
    }
    return ans;
}

LL S2(LL x, LL y) {
    if (prime[y] >= x)
        return 0;
    int p = (x <= sq ? id1[x] : id2[n / x]);
    int ans = mul(4, dec(g[p], gprime[y]));
    for (int i = y + 1; i <= cnt && 1ll * prime[i] * prime[i] <= x; i++) {
        LL pkx = prime[i];
        for (int k = 1; pkx <= x; k++, pkx *= prime[i]) {
            LL pkxm = pkx % mod;
            ans = add(ans, mul(pkxm, mul(add(k, 1), mul(add(k, 1), S2(x / pkx, i) + (k > 1)))));
        }
    }
    return ans;
}

signed main() {
    int T;
    scanf("%d", &T);
    LL inv2 = qkpow(2, mod - 2, mod);
    while (T--) {
        scanf("%lld", &n);
        sq = sqrt(n * 1.0);
        cnt = size = 0;
        for (int i = 0; i <= sq; i++) vis[i] = id1[i] = id2[i] = gprime[i] = g[i] = 0;
        for (int i = 2; i <= sq; i++) {
            if (!vis[i])
                prime[++cnt] = i, gprime[cnt] = add(gprime[cnt - 1], i);
            for (int j = 1; j <= cnt && prime[j] * i <= sq; j++) {
                vis[i * prime[j]] = 1;
                if (i % prime[j] == 0)
                    break;
            }
        }
        for (LL l = 1, r; l <= n; l = r + 1) {
            r = n / (n / l);
            num[++size] = n / r;
            LL Num = (n / r) % mod;
            g[size] = mul(4, Num - 1);
            if (n / r <= sq)
                id1[n / r] = size;
            else
                id2[r] = size;
        }
        for (int i = 1; i <= cnt; i++) {
            LL sqr = 1ll * prime[i] * prime[i];
            for (int j = 1; j <= size && num[j] >= sqr; j++) {
                LL p = num[j] / prime[i];
                p = (p <= sq ? id1[p] : id2[n / p]);
                g[j] = dec(g[j], dec(g[p], mul(4, dec(i, 1))));
            }
        }
        LL totans = mul(add(n % mod, 1), add(S1(n, 0), 1));
        size = 0;
        for (LL l = 1, r; l <= n; l = r + 1) {
            r = n / (n / l);
            num[++size] = n / r;
            LL Num = (n / r) % mod;
            g[size] = dec(mul(Num, mul(add(Num, 1), inv2)), 1);
            if (n / r <= sq)
                id1[n / r] = size;
            else
                id2[r] = size;
        }
        for (int i = 1; i <= cnt; i++) {
            LL sqr = 1ll * prime[i] * prime[i];
            for (int j = 1; j <= size && num[j] >= sqr; j++) {
                LL p = num[j] / prime[i];
                p = (p <= sq ? id1[p] : id2[n / p]);
                g[j] = dec(g[j], mul(prime[i], dec(g[p], gprime[i - 1])));
            }
        }
        totans = dec(totans, add(S2(n, 0), 1));
        printf("%lld\n", totans);
    }
    return 0;
}