A (two)
(1.1) (Description)
你有两棵有根树，每棵各有 n 个顶点。让我们用整数 1 到 n 给每棵树的顶点编
号。两棵树的根都是顶点 1。第一棵树的边都都是蓝色，第二棵树的边都是红色。
简明起见，我们称第一棵树是蓝色的，以及第二棵树是红色的。
当满足下面的两个条件下，我们认为边(x, y) 有害于边(p,q)：
1.边(x,y)的颜色不同于边(p,q)。
2.考虑与边(p, q) 颜色相同的树，编号为 x, y 的两个顶点中有且只有一个同时在
顶点 p 的子树与顶点 q 的子树里。
现在告诉你，在阶段 1，有恰好一条蓝色的边被删除了，
而在阶段 i，若我们删除了边(u 1 ，v 1 )， (u 2 ，v 2 )，... ， (u k ，v k )。
那么在阶段 i+1 我们要删除的所有满足以下条件的边(x,y):
1.边(x,y)未被删除。
2.存在一个 i(i ≤ k)使得边(x,y)有害于(u i ,v i )。
当某个阶段没有删除任何边时，则整个过程结束，你需要回答，每个阶段哪些边
将被删除。
注意，有害边的定义只依赖于开始删边之前的初始就拥有的两棵有根树。
(1.2) (Task)
(1.2.1) (Input)
输入第一行为整数 n，表示两棵树的顶点数目。
接下来的一行包含 n-1 个正整数a 2 ,a 3 ,...,a n (1 ≤ a i ≤ n;a i 不等于 i)，描述第一
棵树的边。数字a i 意味着第一棵树有一条边连接顶点a i 和顶点 i。
接下来的一行包含 n-1 个正整数b 2 ,b 3 ,...,b n (1 ≤ b i ≤ n;b i 不等于 i)，描述第二
棵树的边。数字b i 意味着第一棵树有一条边连接顶点b i 和顶点 i。
接下来的再一行包含一个整数 idx(1 ≤ idx < n)表示在第一阶段中删除的蓝树的
边的编号。我们让每棵树的每条边按照他们在输入中的前后顺序从 1 到 n-1 编
号。
(1.2.2) (Output)
对于每个阶段输出两行。如果这个阶段删除的边是蓝色的，那么对应这一阶段的
两行中，第一行必须为单词 Blue，否则为单词 Red。对应的第二行包含所有此阶
段删除的边的编号，按数字递增顺序输出。
(1.3) (Sample)
1.3.1 Input
5
1 1 1 1
4 2 1 1
3
1.3.2$ $Output
Blue
3
Red
1 3
Blue
1 2
Red
2
(1.4) (Constraint)
对于30%的数据，n<=10;
对于60%的数据，n<=1000。
对于100%的数据，n<=200000。
(60分做法)
直接O(n^2)枚举所有对应的边判断好坏，
然后随便模拟一下就好。
(100分做法)
考虑两棵树的dfs序。
假设要删红边（蓝边同理）：
考虑题目条件：设p是q的父亲，那么坏边的定义化为dfs序就是：
(id[x]>=id[q]&&id[x]<=id[q]+siz[q]-1)+(id[y]>=id[q]&&id[y]<=id[q]+siz[q]-1)==1
应该不用多解释。
令(u[i]=min{id[x],id[y]},v[i]=max{id[x],id[y]})
发现每段待查区间的dfs序是连续的，可以想到用线段树维护区间信息。
我们开两颗线段树，一颗以u[x]为下标，每个区间用vector几下u[x]
在[l,r]区间的所有边的信息（这里说的（x,y）是红树上的边），以v[x]升序排列；
另一颗也差不多。
每次查询时，分别删去第一颗线段树vector里l<=u[i]<=r,且v[i]>r的部分（这一段在vector里是连续的一段，二分位置就好），
以及第二课线段树里l<=v[i]<=r,且u[i]<l的部分，这段也是连续的。
注意要判重，避免重复删除。
复杂度：
每条边在线段树里出现(logn)次，每次查询是O(log^2n的），每条边最多引发一次查询，
所以时间复杂度为O(nlog^2n)，空间复杂度为O(nlogn)。
很考验代码能力的一道题~~
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
I read(int &res){
res=0;re g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
#define T e[k].to
typedef pair<int,int>pii;
int n,m,X,Y,P;
priority_queue<int>q1,q2;
namespace A{
struct E{
int to,nt;
}e[202000];
struct P{
int x,y,id;
}p[202000];
inline bool bb1(P a,P b){
return a.x==b.x?a.y<b.y:a.x<b.x;
}
inline bool bb2(P a,P b){
return a.y==b.y?a.x<b.x:a.y<b.y;
}
vector<P>tr[808000],t[808000];int laz[808000],l1[808000];
int head[202000],fa[202000],id[202000],siz[202000],vis[202000],tot;
int cnt,s[4020000],sn;
I add(int x,int y){
e[++tot].to=y;
e[tot].nt=head[x];
head[x]=tot;
}
I D_1(int x){
id[x]=++tot;siz[x]=1;//cout<<x<<":"<<id[x]<<endl;
for(re k=head[x];k!=-1;k=e[k].nt){
D_1(T);
siz[x]+=siz[T];
}
}
#define all 1,1,n
#define lt k<<1,l,mid
#define rt k<<1|1,mid+1,r
I build(int k,int l,int r){
if(l==r)return;
re mid=(l+r)>>1;
if(!tr[k].empty()){
F(i,0,tr[k].size()-1){
if(tr[k][i].x<=mid)tr[k<<1].emplace_back(tr[k][i]);
else tr[k<<1|1].emplace_back(tr[k][i]);
}
}
if(!t[k].empty()){
F(i,0,t[k].size()-1){
if(t[k][i].y<=mid)t[k<<1].emplace_back(t[k][i]);
else t[k<<1|1].emplace_back(t[k][i]);
}
}
build(lt);
build(rt);
}
I modi(int k,int l,int r,int x,int y){
if(x>r||y<l)return;
if(x<=l&&r<=y){
//cout<<"h"<<tr[k].size()<<" "<<t[k].size()<<endl;
re posl,posr,mid;
if(!tr[k].empty()){
posl=0,posr=tr[k].size()-1;
while(posl!=posr){
mid=(posl+posr)>>1;
if(tr[k][mid].y<=y)posl=mid+1;
else posr=mid;
}
if(tr[k][posl].y>y){
F(j,posl,tr[k].size()-1){
s[++cnt]=tr[k][j].id;
// cout<<"@"<<tr[k][j].x<<" "<<tr[k][j].y<<endl;
}
tr[k].erase(tr[k].begin()+posl,tr[k].begin()+(tr[k].size()-1));
}
}
if(!t[k].empty()){
posl=0;posr=t[k].size()-1;
while(posl!=posr){
mid=(posl+posr+1)>>1;
if(t[k][mid].x>=x)posr=mid-1;
else posl=mid;
}
if(t[k][posl].x<x){
F(j,0,posl){
s[++cnt]=t[k][j].id;
// cout<<"$"<<t[k][j].x<<" "<<t[k][j].y<<endl;
}
t[k].erase(t[k].begin()+0,t[k].begin()+posl);
}
}
return;
}
re mid=(l+r)>>1;
modi(lt,x,y);modi(rt,x,y);
}
IN print(){
sn=0;
sort(s+1,s+1+cnt);
F(i,1,cnt){
if(!vis[s[i]]){
if(!sn){
sn=1;printf("Blue
");
}
vis[s[i]]=1;
q1.push(s[i]);
printf("%d ",s[i]);
}
}
if(sn)printf("
");
return sn;
}
I init(){
memset(head,-1,sizeof(head));
tot=0;
F(i,2,n){
read(fa[i]);
add(fa[i],i);
}
tot=0;
D_1(1);
}
I init2(){
sort(p+1,p+n,bb2);
F(i,1,n-1){
tr[1].emplace_back(p[i]);
}
sort(p+1,p+n,bb1);
F(i,1,n-1){
t[1].emplace_back(p[i]);
}
build(all);
F(i,2,n){
p[i-1].x=fa[i];p[i-1].y=i;p[i-1].id=i-1;
}
}
};
namespace B{
struct E{
int to,nt;
}e[202000];
struct P{
int x,y,id;
}p[202000];
inline bool bb1(P a,P b){
return a.x==b.x?a.y<b.y:a.x<b.x;
}
inline bool bb2(P a,P b){
return a.y==b.y?a.x<b.x:a.y<b.y;
}
vector<P>tr[808000],t[808000];int laz[808000],l1[808000];
int head[202000],fa[202000],id[202000],siz[202000],vis[202000],tot;
int cnt,s[4040000],sn;
I add(int x,int y){
e[++tot].to=y;
e[tot].nt=head[x];
head[x]=tot;
}
I D_1(int x){
id[x]=++tot;siz[x]=1;//cout<<x<<":"<<id[x]<<endl;
for(re k=head[x];k!=-1;k=e[k].nt){
D_1(T);
siz[x]+=siz[T];
}
}
#define all 1,1,n
#define lt k<<1,l,mid
#define rt k<<1|1,mid+1,r
I build(int k,int l,int r){
if(l==r)return;
re mid=(l+r)>>1;
if(!tr[k].empty()){
F(i,0,tr[k].size()-1){
if(tr[k][i].x<=mid)tr[k<<1].emplace_back(tr[k][i]);
else tr[k<<1|1].emplace_back(tr[k][i]);
}
}
if(!t[k].empty()){
F(i,0,t[k].size()-1){
if(t[k][i].y<=mid)t[k<<1].emplace_back(t[k][i]);
else t[k<<1|1].emplace_back(t[k][i]);
}
}
build(lt);
build(rt);
}
I modi(int k,int l,int r,int x,int y){
if(x>r||y<l)return;
if(x<=l&&r<=y){
// cout<<"H"<<tr[k].size()<<" "<<t[k].size()<<endl;
re posl,posr,mid;
if(!tr[k].empty()){
posl=0,posr=tr[k].size()-1;
while(posl!=posr){
mid=(posl+posr)>>1;
if(tr[k][mid].y<=y)posl=mid+1;
else posr=mid;
}
if(tr[k][posl].y>y){
F(j,posl,tr[k].size()-1){
s[++cnt]=tr[k][j].id;
// cout<<"@"<<tr[k][j].x<<" "<<tr[k][j].y<<endl;
}
tr[k].erase(tr[k].begin()+posl,tr[k].begin()+(tr[k].size()-1));
}
}
if(!t[k].empty()){
posl=0;posr=t[k].size()-1;
while(posl!=posr){
mid=(posl+posr+1)>>1;
if(t[k][mid].x>=x)posr=mid-1;
else posl=mid;
}
if(t[k][posl].x<x){
F(j,0,posl){
s[++cnt]=t[k][j].id;
// cout<<"$"<<t[k][j].x<<" "<<t[k][j].y<<endl;
}
t[k].erase(t[k].begin()+0,t[k].begin()+posl);
}
}
return;
}
re mid=(l+r)>>1;
modi(lt,x,y);modi(rt,x,y);
}
IN print(){
if(!cnt)return 0;
sn=0;
sort(s+1,s+1+cnt);
F(i,1,cnt){
if(!vis[s[i]]){
if(!sn){
sn=1;printf("Red
");
}
vis[s[i]]=1;
q2.push(s[i]);
printf("%d ",s[i]);
}
}
if(sn)printf("
");
return sn;
}
I init(){
memset(head,-1,sizeof(head));
tot=0;
F(i,2,n){
read(fa[i]);
add(fa[i],i);
}
tot=0;
D_1(1);
}
I init2(){
sort(p+1,p+n,bb2);
F(i,1,n-1){
tr[1].emplace_back(p[i]);
}
sort(p+1,p+n,bb1);
F(i,1,n-1){
t[1].emplace_back(p[i]);
}
build(all);
F(i,2,n){
p[i-1].x=fa[i];p[i-1].y=i;p[i-1].id=i-1;
}
}
};
I init(){
F(i,2,n){
A::p[i-1].x=min(B::id[A::fa[i]],B::id[i]),A::p[i-1].y=max(B::id[A::fa[i]],B::id[i]);A::p[i-1].id=i-1;
B::p[i-1].x=min(A::id[B::fa[i]],A::id[i]),B::p[i-1].y=max(A::id[B::fa[i]],A::id[i]);B::p[i-1].id=i-1;
}
A::init2();
B::init2();
}
int main(){
freopen("two.in","r",stdin);
freopen("two.out","w",stdout);
read(n);
A::init();
B::init();
init();
read(P);
q1.push(P);
printf("Blue
%d
",P);
A::vis[P]=1;
m=0;
while(1){
m++;
if(m&1){
B::cnt=0;
while(!q2.empty())q2.pop();
while(!q1.empty()){
// cout<<"Q:"<<A::p[q1.top()].y<<" "<<A::id[A::p[q1.top()].y]<<" "<<A::id[A::p[q1.top()].y]+A::siz[A::p[q1.top()].y]-1<<endl;
B::modi(all,A::id[A::p[q1.top()].y],A::id[A::p[q1.top()].y]+A::siz[A::p[q1.top()].y]-1),q1.pop();
}
if(!B::print())break;
}
else {
A::cnt=0;
while(!q1.empty())q1.pop();
while(!q2.empty()){
// cout<<"q:"<<B::p[q2.top()].y<<" "<<B::id[B::p[q2.top()].y]<<" "<<B::id[B::p[q2.top()].y]+B::siz[B::p[q2.top()].y]-1<<endl;
A::modi(all,B::id[B::p[q2.top()].y],B::id[B::p[q2.top()].y]+B::siz[B::p[q2.top()].y]-1),q2.pop();
}
if(!A::print())break;
}
}
return 0;
}
/*
5
1 1 1 1
4 2 1 1
3
*/
(B) (bracket)
(2.1) (Description)
给定一棵有 n 个节点的无根树，每个节点上是一个字符，要么是(，要么是)。
定义 S(x, y) 为从 x 开始沿着最短路走到 y，将沿途经过的点上的字符依次连
起来得到的字符串。
合法括号序定义如下:
1，()是合法的。
2合法，则(A)也合法。
3，若 A，B 分别合法，则 AB 也合法。
函数 f(x, y) 等于对 S(x, y) 进行划分，使得每一个部分都是合法括号序，能得
到的最大的段数，比如(())()()的最大段数为 3，(()())(())的最大段数为 2。
特别的，如果 S(x,y)本身并不是合法括号序，则 f(x,y)=0。
m 次询问，每次输入一个 k，查询有多少点对的 f 值为 k。
(2.2) (Task)
(2.2.1) (Input)
第一行一个整数 n，表示节点数。
n-1 行每行两个整数 x,y,描述一条边。
来 n 行，每行一个字符(或)，其中第 i 行表示 i 号节点的字符。
来一行一个整数 m，表示询问个数。
接下来 m 行，每行一个整数 k，表示一个询问。
(2.2.2) (Output)
输出共 m 行，每行一个整数表示有多少对 x，y 满足 f(x,y)=k。
(2.3) $Sample
(2.3.1) (Input)
6
1 2
2 6
4 2
3 4
1 5
)
(
)
(
)
3
1
2
3
(2.3.2) (Output)
4
2
0
(2.4) (Constraint)
对于 30%的数据，n,m≤5000
对于另 30%的数据，m≤10
对于 100%的数据，n,m≤50000
(30分做法)
枚举根节点，暴力dfs即可。复杂度O(n^2)。
(100分做法)
看到这种询问整棵树的信息的题，容易想到点分治。
设当前重心为u。
考虑30分做法的dfs，我们需要维护sum(括号序列前缀和），
cnt（合法划分的个数）。
这里我们要把两个残缺的括号序列拼起来，问题就变成了
如何记录一个残缺的括号序列的合法划分数，以及如何判断其合法性。
我们把待合并的两个括号序列分别叫左序列和右序列。
手膜一下，发现一个性质：对于一个前缀和为sum的左序列，其合法条件为：
这个序列的任意后缀的前缀和（也就是从u到这个节点的过程中的所有前缀和）都<=sum。
而其合法段数cnt即为这个序列所有后缀=sum的个数和-1。
右序列也可以发现类似的性质。
由此，我们可以做两次dfs，求解所有合法的左序列f,右序列g。
每个序列都可以表示为一个二元组（sum,cnt）,sum就是前缀和的绝对值，cnt就是
合法划分数。合并时，对答案k的贡献就是(sum_{i=0}^k)(f[sum][i]*g[sum][k-i])
发现这个东西是卷积的形式，直接用fft搞就好。
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
I read(int &res){
res=0;re g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
typedef double db;
const db pi=acos(-1);
const int INF=1e9+7;
int r[50500];
struct CPX{
db x,y;
CPX(db _x=0.0,db _y=0.0){
x=_x;y=_y;
}
friend CPX operator + (CPX a,CPX b){
register CPX c;
c.x=a.x+b.x;
c.y=a.y+b.y;
return c;
}
friend CPX operator - (CPX a,CPX b){
register CPX c;
c.x=a.x-b.x;
c.y=a.y-b.y;
return c;
}
friend CPX operator * (CPX a,CPX b){
register CPX c;
c.x=a.x*b.x-a.y*b.y;
c.y=a.x*b.y+a.y*b.x;
return c;
}
CPX operator / (const db val){
register CPX c;
c.x=x/val;c.y=y/val;
return c;
}
};
I fft(CPX b[],int n,int sit){
for(re i=0,j=0;i<n;i++){
if(i<j)swap(b[i],b[j]);
re k=n>>1;
while(k&j)j^=k,k>>=1;
j^=k;
}
for(re i=1;i<n;i<<=1){
CPX w1=CPX(cos(pi/i),sin(pi/i)*sit);
for(re j=0;j<n;j+=(i<<1)){
CPX w=CPX(1,0);
for(re l=j,r=j+i;l<j+i;l++,r++,w=w*w1){
CPX t=b[r]*w;
b[r]=b[l]-t;
b[l]=b[l]+t;
}
}
}
if(sit==-1){
F(i,0,n-1){
b[i]=b[i]/n;
}
}
}
struct E{
int to,nt,v;
}e[101000];
#define T e[k].to
char c[50500];
vector<int>f[50500],g[50500];
int n,m,N,maxi,root,fmx,gmx,dep[50500],f0[50500],g0[50500],lg[50500],gl[50500],vis[50500],siz[50500],mx[50500],head[50500],a[50500],tot=-1,X,Y;
ll ans[50500];
I D_3(int x,int fa){
siz[x]=1;dep[x]=1;
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fa||vis[T]||e[k].v)continue;
D_3(T,x);
siz[x]+=siz[T];
dep[x]=max(dep[x],dep[T]+1);
}
}
I findroot(int x,int fa){
siz[x]=1;mx[x]=0;
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fa||vis[T]||e[k].v)continue;
findroot(T,x);
siz[x]+=siz[T];
mx[x]=max(mx[x],siz[T]);
}
mx[x]=max(mx[x],N-siz[x]);
if(maxi>mx[x]){
maxi=mx[x];
root=x;
}
}
I D_1(int x,int fa=0,int sum=0,int cnt=1,int maxsiz=0){
sum+=a[x];
if(sum==maxsiz)cnt++;
if(sum>maxsiz)maxsiz=sum,cnt=1;
if(sum==maxsiz)f[sum].emplace_back(cnt-1+(sum!=0));
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fa||vis[T]||e[k].v)continue;
D_1(T,x,sum,cnt,maxsiz);
}
}
I D_2(int x,int fa=0,int sum=0,int cnt=1,int minsiz=0){
sum+=a[x];
if(sum==minsiz)cnt++;
if(sum<minsiz)minsiz=sum,cnt=1;
if(sum==minsiz)g[-sum].emplace_back(cnt-1);
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fa||vis[T]||e[k].v)continue;
D_2(T,x,sum,cnt,minsiz);
}
}
I calc(int depth,int sit){
static CPX A[101000],B[101000];
F(i,0,depth){
re len1,len2,len;
len1=len2=len=1;
for(auto p:f[i])A[p].x++,len1=max(len1,p+1);
f[i].clear();
for(auto p:g[i])B[p].x++,len2=max(len2,p+1);
g[i].clear();
while(len<len1+len2-1)len<<=1;
fft(A,len,1);
fft(B,len,1);
F(i,0,len-1){
A[i]=A[i]*B[i];
}
fft(A,len,-1);
F(i,0,len1+len2-1){
//cout<<"!"<<i<<"";
ans[i]+=1ll*sit*(ll)floor(A[i].x+0.5);
//cout<<ans[i]<<endl;
}
memset(A,0,sizeof(CPX)*len);
memset(B,0,sizeof(CPX)*len);
}
}
I solve(int x){
D_3(x,0);
for(re k=head[x];k!=-1;k=e[k].nt){
if(vis[T]||e[k].v)continue;
D_1(T,x);
}
f[0].push_back(0);
D_2(x);
calc(dep[x],1);
for(re k=head[x];k!=-1;k=e[k].nt){
if(vis[T]||e[k].v)continue;
D_1(T,x);
D_2(T,x,a[x],1,min(a[x],0));
calc(dep[T]+1,-1);
}
}
I divided(int x){
solve(x);
vis[x]=1;
for(re k=head[x];k!=-1;k=e[k].nt){
if(vis[T]||e[k].v)continue;
e[k].v=e[k^1].v=1;
N=siz[T];
maxi=INF;
findroot(T,x);
divided(root);
}
}
int main(){
freopen("bracket.in","r",stdin);
freopen("bracket.out","w",stdout);
read(n);
tot=-1;
memset(head,-1,sizeof(head));
F(i,1,n-1){
read(X);read(Y);
e[++tot].to=Y;
e[tot].nt=head[X];
head[X]=tot;
e[++tot].to=X;
e[tot].nt=head[Y];
head[Y]=tot;
}
F(i,1,n){
cin>>c[i];
a[i]=(c[i]=='(')?1:-1;
}
N=n;maxi=INF;
findroot(1,0);
divided(root);
read(m);
while(m--){
read(X);
printf("%lld
",ans[X]);
}
return 0;
}
/*
6
1 2
2 6
4 2
3 4
1 5
)
(
)
)
(
)
3
1
2
3
*/
(C) (sum)
(3.1) (Description)
请你取出集合{1, 2, …, n}的一个子集，使得其中的元素两两互质，并最大化子集
中的元素之和，你只需要输出这个子集中的元素之和即可。
如 ans(10)=30，此时的子集为{1, 5, 7, 8, 9}。
(3.2 Task)
(3.2.1 Input)
一行，一个正整数 n
(3.2.2 Output)
一行一个正整数，表示答案
(3.3) (Sample)
(3.3.1) (Input)
10
(3.3.2) (Output)
30
(3.4) (Constraint)
对于30%的数据，1<=n<=30
对于80%的数据，1<=n<=800
对于100%的数据，1<=n<=200000
话说80分是真滴良心啊。
(80分做法)
首先，肯定要尽量多的选质数，然后选合数的话，
其质因子也不能超过2个。且一个<= √n,一个>= √n
跑个费用流就好。
。。。满分做法待填坑，先提供std代码一份：
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=400005,M=400005,inf=1047483647;
struct node { int y,z,c,next; } a[M<<2];
LL dis[M],an;
int b[M],la[M],d[M],q[M+100],D[N],pr[N],head[M],i,j,k,n,m,J,s,e,z,X,l,r,g;
bool p[N];
char c;
inline char getc()
{
#define VV 10000000
static char s[VV],*l=s,*r=s;
if (l==r)
l=s,r=s+fread(s,1,VV,stdin);
return *l++;
}
int read(){ int z=0; do c=getchar(); while (c<'0'||c>'9'); while (c>='0'&&c<='9') z*=10,z+=c-'0',c=getchar(); return z; }
void jb(int x,int y,int z,int c)
{
a[++k]=(node){y,z,c,head[x]},head[x]=k,
a[++k]=(node){x,0,-c,head[y]},head[y]=k;
}
int plus(int z){ return z<M+50?z+1:1; }
bool SPFA()
{
for (register int i=1;i<=e;++i) dis[i]=-inf,p[i]=0;
p[q[l=r=1]=s]=1,dis[s]=0;
for (;l!=plus(r);l=plus(l))
{
int d=q[l];
for (register int j=head[d];j;j=a[j].next)
if (a[j].z)
{
int c=a[j].y;
if (dis[c]<dis[d]+a[j].c)
{
dis[c]=dis[d]+a[j].c,la[c]=d,b[c]=j;
if (!p[c])
p[q[r=plus(r)]=c]=1;
}
}
p[d]=0;
}
return dis[e]>0;
}
void addflow()
{
for (register int i=e;i!=s;i=la[i]) --a[b[i]].z,++a[b[i]^1].z;
an+=dis[e];
}
int main(){
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
n=read();
X=sqrt(n);
for (i=2;i<=n;++i)
{
if (!p[i]) pr[++g]=i;
for (j=1;j<=g&&pr[j]<=n/i;++j)
{
p[i*pr[j]]=1;
if (!(i%pr[j])) break;
}
}
for (J=0;pr[J+1]<=X;++J);
for (i=1;i<=J;an+=D[i],++i)
for (D[i]=pr[i];D[i]*pr[i]<=n;D[i]*=pr[i]);
for (;i<=g;++i) an+=pr[i];
s=g+1,e=s+1,k=1;
for (i=1;i<=J;++i) jb(s,i,1,0);
for (;i<=g;++i) jb(i,e,1,0);
int d;
for (j=J+1;j<=g;++j)
for (i=1;i<=J;++i)
{
z=n/pr[j];
for (d=1;d*pr[i]<=z;d*=pr[i]);
if (d*pr[j]>D[i]+pr[j])
jb(i,j,1,d*pr[j]-D[i]-pr[j]);
}
while (SPFA()) addflow();
printf("%lld
",an+1);
return 0;
}