[BZOJ 3339]Rmq Problem
万恶的标题党啊~
这个题明显扫描线辣……但是怎么扫呢？
我们可以考虑对于每个前缀区间[tex][1,r][/tex]先求出他们的[tex]mex[/tex]值，然后用线段树维护。
从[tex][l,r][/tex]转移到[tex][l+1,r][/tex]时，需要将[tex][l,next[l]-1][/tex]（[tex]next[l][/tex]是下一个和[tex]l[/tex]具有相同值的位置）中的所有大于[tex]A[l][/tex]（[tex]l[/tex]的值）的值全部变为[tex]A[l][/tex]。但是这一步怎么做啊……难道要用Segment Beats？
答案是否定的。注意到我们真正需要的只是叶子结点，所以其他非叶子结点的最小值全部弄成无限大，然后这样做就可以把最小值当做标记来弄了……非常精巧。
代码：
/**************************************************************
Problem: 3339
User: danihao123
Language: C++
Result: Accepted
Time:1988 ms
Memory:10396 kb
****************************************************************/
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=200005,INF=0x7f7f7f7f;
const int maxnode=maxn*4;
int A[maxn];
int minv[maxnode];
void build_tree(int o,int L,int R){
if(L==R){
minv[o]=A[L];
}else{
int M=L+(R-L)/2;
minv[o]=INF;
build_tree(o<<1,L,M);
build_tree(o<<1|1,M+1,R);
}
}
inline void paint(int o,int v){
minv[o]=min(minv[o],v);
}
inline void pushdown(int o){
paint(o<<1,minv[o]);
paint(o<<1|1,minv[o]);
minv[o]=INF;
}
int pos;
int query(int o,int L,int R){
if(L==R)
return minv[o];
if(minv[o]<INF)
pushdown(o);
int M=L+(R-L)/2;
if(pos<=M)
return query(o<<1,L,M);
else
return query(o<<1|1,M+1,R);
}
int ql,qr,v;
void update(int o,int L,int R){
if(ql<=L && R<=qr){
paint(o,v);
}else{
if(minv[o]<INF)
pushdown(o);
int M=L+(R-L)/2;
if(ql<=M)
update(o<<1,L,M);
if(qr>M)
update(o<<1|1,M+1,R);
}
}
inline int readint(){
register int x=0;
register char c;
fread(&c,1,1,stdin);
while(!isdigit(c))
fread(&c,1,1,stdin);
while(isdigit(c)){
x=x*10+c-'0';
fread(&c,1,1,stdin);
}
return x;
}
int buf[21];
inline void putint(int x){
register int i,p=0;
if(!x){
buf[p++]=0;
}else{
while(x){
buf[p++]=x%10;
x/=10;
}
}
for(i=p-1;i>=0;i--)
putchar(buf[i]+'0');
putchar('\n');
}
bool vis[maxn];
int last[maxn],next[maxn];
struct Query{
int id;
int l,r;
int ans;
};
bool cmp1(const Query& x,const Query& y){
if(x.l==y.l)
return x.r<y.r;
else
return x.l<y.l;
}
bool cmp2(const Query& x,const Query& y){
return x.id<y.id;
}
Query QS[maxn];
int V[maxn];
int main(){
int n,q;
register int i,l=1,k=0;
n=readint();
q=readint();
for(i=1;i<=n;i++){
V[i]=readint();
vis[V[i]]=true;
if(k==V[i])
while(vis[k])
k++;
A[i]=k;
}
build_tree(1,1,n);
for(i=n;i>=1;i--){
if(!last[V[i]])
next[i]=n+1;
else
next[i]=last[V[i]];
last[V[i]]=i;
}
for(i=1;i<=q;i++){
QS[i].id=i;
QS[i].l=readint();
QS[i].r=readint();
}
sort(QS+1,QS+1+q,cmp1);
for(i=1;i<=q;i++){
while(l<QS[i].l){
ql=l;
qr=next[l]-1;
v=V[l];
update(1,1,n);
l++;
}
pos=QS[i].r;
QS[i].ans=query(1,1,n);
}
sort(QS+1,QS+1+q,cmp2);
for(i=1;i<=q;i++){
putint(QS[i].ans);
}
return 0;
}
[BZOJ 1468]Tree
点分治第一题……
这个也就是最经典的那个点分治问题了吧……参照qzc大爷的论文吧。
代码：
/**************************************************************
Problem: 1468
User: danihao123
Language: C++
Result: Accepted
Time:816 ms
Memory:2736 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 40005;
const int maxm = maxn * 2;
struct Edge {
Edge *next;
int to, dist;
};
Edge pool[maxm];
int graph_cnt;
Edge *first[maxn];
inline void clear_graph() {
graph_cnt = 0;
memset(first, 0, sizeof first);
}
inline void add_edge(int u, int v, int d) {
Edge *e = &pool[graph_cnt++];
e->next = first[u];
first[u] = e;
e->to = v;
e->dist = d;
}
int k;
int calc(vector<int>& V) {
int size = V.size();
int rc = size - 1;
int ans = 0;
if(size <= 1){
return 0;
}
for(int i = 0; i < size; i++) {
while(i < rc && V[i] + V[rc] > k) {
rc--;
}
if(i == rc) {
break;
}
ans += rc - i;
}
return ans;
}
bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int fa) {
siz[x] = 1;
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
gen_siz(v, x);
siz[x] += siz[v];
}
}
}
int now_root, best_root;
void gen_best_root(int x, int fa) {
bool OK = siz[x]*2 >= siz[now_root];
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
gen_best_root(v, x);
OK = OK && (siz[v]*2 <= siz[now_root]);
}
}
if(OK) {
best_root = x;
}
}
void add_to_V(int x, int fa, int d, vector<int>& V) {
V.push_back(d);
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(!vis[v] && v != fa) {
add_to_V(v, x, d + e->dist, V);
}
}
}
int divide(int x) {
gen_siz(x, 0);
now_root = x;
gen_best_root(x, 0);
x = best_root;
vis[x] = true;
vector<int> V, CV;
int ans = 0;
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(vis[v]) {
continue;
}
CV.clear();
add_to_V(v, x, e->dist, CV);
sort(CV.begin(), CV.end());
ans -= calc(CV);
for(int i = 0; i < CV.size(); i++) {
V.push_back(CV[i]);
}
}
V.push_back(0);
sort(V.begin(), V.end());
ans += calc(V);
for(Edge *e = first[x]; e; e = e->next) {
int v = e->to;
if(vis[v]) {
continue;
}
ans += divide(v);
}
return ans;
}
int main() {
int n;
scanf("%d", &n);
clear_graph();
for(int i = 1; i <= (n - 1); i++) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
add_edge(u, v, d);
add_edge(v, u, d);
}
scanf("%d", &k);
printf("%d\n", divide(1));
return 0;
}
[BZOJ 1051]受欢迎的牛
Tarjan缩点第一题……
很容易想到找出度为0的点（当且仅当这样的点有一个时有解），但是在有环图上这个方法会失效。
处理方法是，用Tarjan的强联通分量算法求出所有SCC，然后把每个SCC缩成一个点，然后再在缩点之后的图上求解即可（这个图是DAG。原因很简单，要是有环还能接着缩）。
代码：
/**************************************************************
Problem: 1051
User: danihao123
Language: C++
Result: Accepted
Time:72 ms
Memory:1692 kb
****************************************************************/
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=50005;
int first[maxn];
int next[maxm],to[maxm];
int graph_cnt=0;
inline void AddEdge(int u,int v){
graph_cnt++;
next[graph_cnt]=first[u];
first[u]=graph_cnt;
to[graph_cnt]=v;
}
int pre[maxn],low[maxn],sccno[maxn],sccsiz[maxn];
stack<int> S;
int dfs_clk=0,scc_cnt=0;
void dfs(int x){
dfs_clk++;
pre[x]=low[x]=dfs_clk;
S.push(x);
int i,u;
for(i=first[x];i;i=next[i]){
u=to[i];
if(!pre[u]){
dfs(u);
low[x]=min(low[x],low[u]);
}else{
if(!sccno[u])
low[x]=min(low[x],pre[u]);
}
}
if(low[x]==pre[x]){
scc_cnt++;
sccsiz[scc_cnt]=0;
while(true){
u=S.top();
S.pop();
sccno[u]=scc_cnt;
sccsiz[scc_cnt]++;
if(u==x)
break;
}
}
}
int n;
inline void Tarjan(){
register int i;
for(i=1;i<=n;i++)
if(!pre[i])
dfs(i);
}
bool Out[maxn];
int main(){
int m,u,v;
register int i,j,ans=0;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&u,&v);
AddEdge(u,v);
}
Tarjan();
for(i=1;i<=n;i++){
for(j=first[i];j;j=next[j]){
u=to[j];
if(sccno[i]!=sccno[u])
Out[sccno[i]]=true;
}
}
for(i=1;i<=scc_cnt;i++){
if(!Out[i]){
if(ans){
ans=0;
break;
}
ans=sccsiz[i];
}
}
if(n==1)
ans=0;
printf("%d\n",ans);
return 0;
}
[BZOJ 3172]单词
首先……出题人语文不太好……估计和我这种语文很差的人还有差距……
这个提的意思是，给你若干个单词，输出每个单词在所有单词（而不是把所有单词连起来）中出现的次数。
然后肯定要AC自动机上失配函数搞一波辣……把BFS序倒过来搜，传递出现次数即可。还有这个题的数据范围好像也比给出的小很多……
代码：
/**************************************************************
Problem: 3172
User: danihao123
Language: C++
Result: Accepted
Time:232 ms
Memory:115080 kb
****************************************************************/
#include <cstdio>
#include <cstring>
const int maxn=205;
const int maxnode=1*1e6+5;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int cnt[maxnode];
namespace ACAutomate{
// Trie
const int sigma_size=26;
int Tree[maxnode][sigma_size];
int siz;
inline int idx(char c){
return c-'a';
}
void InitAC(){
siz=0;
CL_ARR(Tree[0],0);
}
int Insert(char *s){
register int i,n=strlen(s);
register int u=0,c;
REP(i,n){
c=idx(s[i]);
if(!Tree[u][c]){
siz++;
Tree[u][c]=siz;
CL_ARR(Tree[siz],0);
}
u=Tree[u][c];
cnt[u]++;
}
return u;
}
// AC Automate
int f[maxnode];
int Q[maxnode];
void InitFail(){
register int i,u,x,v,head=0,tail=0;
f[0]=0;
REP(i,sigma_size){
u=Tree[0][i];
if(u){
f[u]=0;
Q[tail++]=u;
}
}
while(head<tail){
u=Q[head];
head++;
REP(i,sigma_size){
x=Tree[u][i];
if(!x){
continue;
}
Q[tail++]=x;
v=f[u];
while(v && !Tree[v][i])
v=f[v];
f[x]=Tree[v][i];
}
}
for(i=tail-1;i>=0;i--)
cnt[f[Q[i]]]+=cnt[Q[i]];
}
};
char buf[maxnode];
int pos[maxn];
int main(){
int n;
register int i;
scanf("%d",&n);
ACAutomate::InitAC();
REP_B(i,n){
scanf("%s",buf);
pos[i]=ACAutomate::Insert(buf);
}
ACAutomate::InitFail();
REP_B(i,n){
printf("%d\n",cnt[pos[i]]);
}
return 0;
}
[BZOJ 1511]Periods of Words
很妙的一道题啊。
这个题可以先求一遍KMP的失配函数，然后对于每个失配函数沿着失配边往前一直走（不能走到0）。然后对于每个前缀[tex]i[/tex]，答案就是[tex]i-f[i][/tex]（要求[tex]f[i][/tex]不为0，反之无解）。
为什么这样可以呢？
首先建议大家看一下Matrix67关于KMP的解释。对于一个前缀，如果整个弄上去肯定不行。所以说需要前面和后面重叠一个字串，这个子串是不考虑的。当然，我们希望在这个被删除的子串最短辣。
代码：
/**************************************************************
Problem: 1511
User: danihao123
Language: C++
Result: Accepted
Time:148 ms
Memory:5704 kb
****************************************************************/
#include <cstdio>
const int maxn=1000005;
char buf[maxn];
int f[maxn];
int main(){
register int i,j;
register long long ans=0;
int n;
scanf("%d%s",&n,buf);
f[0]=f[1]=0;
for(i=1;i<n;i++){
j=f[i];
while(j && buf[i]!=buf[j])
j=f[j];
f[i+1]=(buf[i]==buf[j]?j+1:0);
}
for(i=2;i<=n;i++){
if(f[i]){
while(f[f[i]]){
f[i]=f[f[i]];
}
}
}
for(i=1;i<=n;i++){
if(f[i]){
ans+=i-f[i];
}
}
printf("%lld\n",ans);
return 0;
}
[BZOJ 1212]L语言
这个感觉本质上和那个Remember a Word很像吧……
不过这个只是求最长可行前缀，递推即可。
代码：
/**************************************************************
Problem: 1212
User: danihao123
Language: C++
Result: Accepted
Time:660 ms
Memory:45072 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=1048581;
const int maxW=4005,maxL=105;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
vector<int> AnsList;
namespace Trie{
const int maxnode=400005;
const int sigma_siz=26;
int Tree[maxnode][sigma_siz];
int val[maxnode];
int siz;
inline int idx(char c){
return c-'a';
}
inline void InitTrie(){
siz=0;
val[0]=0;
CL_ARR(Tree[0],0);
}
void Insert(char *s,int v){
register int u=0,n=strlen(s);
register int i,c;
REP(i,n){
c=idx(s[i]);
if(!Tree[u][c]){
siz++;
Tree[u][c]=siz;
val[siz]=0;
CL_ARR(Tree[siz],0);
}
u=Tree[u][c];
}
val[u]=v;
}
void Query(char *s,int len){
register int i,c,u=0;
AnsList.clear();
REP(i,len){
if(!s[i])
break;
c=idx(s[i]);
if(!Tree[u][c])
break;
u=Tree[u][c];
if(val[u])
AnsList.push_back(val[u]);
}
}
};
char Text[maxn];
int len[maxW];
char buf[maxL];
bool d[maxn];
int main(){
int n,m;
int length;
register int i,j,k;
bool flag;
Trie::InitTrie();
scanf("%d%d",&n,&m);
REP_B(i,n){
scanf("%s",buf);
len[i]=strlen(buf);
Trie::Insert(buf,i);
}
REP_B(i,m){
scanf("%s",Text);
length=strlen(Text);
CL_ARR(d,0);
d[0]=true;
for(j=0;j<=length;j++){
if(d[j]){
Trie::Query(Text+j,length-j);
REP(k,AnsList.size()){
d[j+len[AnsList[k]]]=true;
}
}
}
flag=false;
for(j=length;j>=0;j--){
if(d[j]){
flag=true;
printf("%d\n",j);
break;
}
}
if(!flag)
puts("0");
}
return 0;
}
[BZOJ 2081]Beads
Hash第一题……
这个题直接枚举串长Hash判断即可。不过，注意读题。
感觉Hash挺简单的。还有就是我用了wyy的生日做Hash种子辣！
代码：
/**************************************************************
Problem: 2081
User: danihao123
Language: C++
Result: Accepted
Time:5636 ms
Memory:10904 kb
****************************************************************/
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const int maxn=200005;
const ull x=200261;
ull s[maxn];
ull sufHash[maxn],preHash[maxn],x_pow[maxn];
int n;
inline void InitHash(){
register int i;
for(i=n;i>=1;i--){
sufHash[i]=s[i]+sufHash[i+1]*x;
}
for(i=1;i<=n;i++){
preHash[i]=s[i]+preHash[i-1]*x;
}
x_pow[0]=1;
for(i=1;i<=n;i++){
x_pow[i]=x*x_pow[i-1];
}
}
inline ull Hash(int i,int L){
return sufHash[i]-x_pow[L]*sufHash[i+L];
}
inline ull FilpHash(int i,int L){
return preHash[i+L-1]-x_pow[L]*preHash[i-1];
}
set<ull> S;
vector<int> AnsList;
int tot=0;
inline void Check(int k){
register int i,ans=0;
register ull h;
S.clear();
for(i=1;(i+k-1)<=n;i+=k){
h=Hash(i,k)*FilpHash(i,k);
if(!S.count(h)){
S.insert(h);
ans++;
}
}
if(ans>tot){
tot=ans;
AnsList.clear();
AnsList.push_back(k);
}else{
if(ans==tot)
AnsList.push_back(k);
}
}
int main(){
register int i,ans=0,maxv=0,cnt,temp;
bool flag;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%llu",&s[i]);
InitHash();
for(i=1;i<=n;i++){
Check(i);
}
printf("%d %d\n",tot,AnsList.size());
flag=false;
for(i=0;i<AnsList.size();i++){
if(flag)
putchar(' ');
flag=true;
printf("%d",AnsList[i]);
}
putchar('\n');
return 0;
}
[BZOJ 2118]墨墨的等式
论如何把数论乱搞和图论乱搞出在一起……
这个题由于要求[tex]x\ge 0[/tex]，所以不能gcd乱搞。我们可以先取[tex]\{a_n\}[/tex]的最小值[tex]p[/tex]（忽略为0的情况，为啥取最小值待会再说），对方程两边模[tex]p[/tex]。然后对于任何能使某个同余方程成立的[tex]\{x_n\}[/tex]，将其中所有[tex]x_i[/tex]同时加任意个[tex]p[/tex]，同余方程都成立。
取模后，[tex]B\in Z_p[/tex]，所以说只要对于[tex]Z_p[/tex]中的每个数找出最小的一组合法解即能推出其他解（所以说，剩余系越少效率越高，这也就要求取的[tex]a_i[/tex]要小）。不过这个最小的一组合法解怎么找？
我们先找出任意一个合法[tex]B[/tex]（比如说0吧），然后尝试加上[tex]a_i[/tex]，就可以推出其他[tex]B\in Z_p[/tex]的最小解。这个应用当然是需要最短路辣。
求出来的最短路，表示的是取最小解时的[tex]B[/tex]。这样的话就可以推出某个前缀区间中合法[tex]B[/tex]的个数（能加多少[tex]p[/tex]，就有多少个，注意不要忽略加0个的情况），并且答案符合区间减法，最后做差分即可。
注意忽略[tex]a_i=0[/tex]的情况（相当于不存在）。
代码：
/**************************************************************
Problem: 2118
User: danihao123
Language: C++
Result: Accepted
Time:1952 ms
Memory:5508 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
typedef long long ll;
const int maxn=15;
const ll INF=0x7f7f7f7f7f7f7f7f;
ll A[maxn];
bool inQueue[500005];
ll d[500005];
int n;
ll minv;
inline void SPFA(){
register int i,u,to;
queue<int> Q;
memset(d,0x7f,sizeof(d));
d[0]=0;
Q.push(0);
inQueue[0]=true;
#ifdef DEBUG
assert(d[1]==INF);
#endif
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
for(i=1;i<=n;i++){
to=(u+A[i])%minv;
if(d[u]<INF && d[u]+A[i]<d[to]){
d[to]=d[u]+A[i];
if(!inQueue[to]){
Q.push(to);
inQueue[to]=true;
}
}
}
}
}
inline ll Calc(ll x){
register ll ans=0;
register int i=0;
for(i=0;i<minv;i++)
if(d[i]<=x)
ans+=(x-d[i])/minv+1;
return ans;
}
int main(){
ll l,r;
register int i;
scanf("%d%lld%lld",&n,&l,&r);
minv=0x7fffffff;
for(i=1;i<=n;i++){
scanf("%d",&A[i]);
if(!A[i]){
i--;
n--;
continue;
}
minv=min(minv,A[i]);
}
SPFA();
printf("%lld\n",Calc(r)-Calc(l-1));
return 0;
}
[BZOJ 1711]吃饭
这道题当初竟然没A……so sad
这题的建图要这么来：吃的、喝的、牛什么的统统拉进图里（不过牛本身只能同时享受一种食物，所以说点容量为1，要拆成俩点）。对于吃的，从[tex]S[/tex]向每个吃的连一条边。喝的每个向[tex]T[/tex]连一条边。牛本身按照喜好连即可（注意要拆成俩点！）。
代码：
/**************************************************************
Problem: 1711
User: danihao123
Language: C++
Result: Accepted
Time:20 ms
Memory:864 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn=405,INF=0x7f7f7f7f;
namespace Dinic{
struct Edge{
int u,v,cap,flow;
};
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int d[maxn];
int s,t;
bool BFS(){
register int i,x;
queue<int> Q;
memset(vis,0,sizeof(vis));
d[s]=0;
Q.push(s);
vis[s]=true;
while(!Q.empty()){
x=Q.front();
Q.pop();
for(i=0;i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(!vis[e.v] && e.cap>e.flow){
d[e.v]=d[x]+1;
Q.push(e.v);
vis[e.v]=true;
}
}
}
return vis[t];
}
int cur[maxn];
int DFS(int x,int a){
if(x==t || a==0)
return a;
int flow=0,f;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[e.v]==d[x]+1){
f=DFS(e.v,min(a,e.cap-e.flow));
if(f>0){
flow+=f;
e.flow+=f;
edges[G[x][i]^1].flow-=f;
a-=f;
if(a==0)
break;
}
}
}
return flow;
}
inline int Maxflow(int S,int T){
register int ans=0;
s=S;
t=T;
while(BFS()){
memset(cur,0,sizeof(cur));
ans+=DFS(s,INF);
}
return ans;
}
};
int main(){
int N,F,D,f,d,x;
register int i,j,t;
scanf("%d%d%d",&N,&F,&D);
t=2*N+F+D+1;
for(i=1;i<=F;i++)
Dinic::AddEdge(0,i,1);
for(i=2*N+F+1;i<t;i++)
Dinic::AddEdge(i,t,1);
for(i=1;i<=N;i++)
Dinic::AddEdge(F+2*i-1,F+2*i,1);
for(i=1;i<=N;i++){
scanf("%d%d",&f,&d);
for(j=1;j<=f;j++){
scanf("%d",&x);
Dinic::AddEdge(x,2*i-1+F,1);
}
for(j=1;j<=d;j++){
scanf("%d",&x);
Dinic::AddEdge(2*i+F,F+2*N+x,1);
}
}
printf("%d\n",Dinic::Maxflow(0,t));
return 0;
}
[BZOJ 2190]仪仗队
这个题啊……有规律可循。
我们可以发现，关于答案[tex]a[/tex]有如下规律：
[tex]a+1=2\mul (\Sigma_{i=2}^{n-1}\varphi(i)+2)[/tex]
然后筛法求欧拉函数即可（我听说神犇们都用了杜教筛哎）
代码：
/**************************************************************
Problem: 2190
User: danihao123
Language: C++
Result: Accepted
Time:28 ms
Memory:976 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=40005;
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
int phi[maxn];
int n;
void sieve(){
register int i,j;
phi[1]=1;
CUS_REP(i,2,n)
if(!phi[i])
for(j=i;j<=n;j+=i){
if(!phi[j])
phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}
int main(){
register int i,ans=2;
scanf("%d",&n);
sieve();
/*
#ifdef DEBUG
CUS_REP(i,1,n)
printf("%d\n",phi[i]);
#endif
*/
CUS_REP(i,2,n-1)
ans+=phi[i];
printf("%d\n",ans*2-1);
return 0;
}
