相关链接
题目传送门：http://paste.ubuntu.com/24087843/
数据生成器：http://paste.ubuntu.com/24087850/
std：http://paste.ubuntu.com/24087841/
题目大意
给定$1 \sim n$的排列$a_i$，再给定$m$个询问、每次给出$l_i,r_i$
求$\sum\limits_{i=l_i}^{r_i}{\sum\limits_{j=l_i}^{i-1}{gcd(a_i,a_j)}}$, $n,m \le 2 \cdot 10^4$
解题报告
一看数据范围就给人一种大暴力的感觉
但用$O(1)$的$GCD$做到$O(nk)$并不能通过此题
std的话非常套路啊！
考虑维护一个集合，支持加入、删除、查询集合中的数两两$GCD$的和
如果可以在$O(\log n)$的时间复杂度完成维护的话，显然可以用莫队做到$O(n^{1.5} \log n)$
现在考虑如何维护，如果分解因数的话，会有算重的部分
但我们列出式子，发现我们计算的实际是：$\sum\limits_{d|gcd(a_i,a_j)}{f(d)}$
如果窝萌把$f(d)$令成$\varphi (d)$，那岂不是刚刚好？
于是我们对于删除和加入，枚举因数$i$，然后在第i个位置加入$\varphi (i)$即可
那么总的复杂度均摊下来是$O(n^{1.5} \log n)$的
另外本题还有一个兄弟版本：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1439
就是要求维护一个集合中两两互质的对数，把$\varphi(i)$换成$\mu(i)$就是一样的做法了
全™是套路啊！
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100009;
LL vout[N],cnt[N],ans;
int n,m,tot,BLK,pri[N],arr[N],phi[N];
vector<int> divs[N]; bool vis[N];
struct Query{int l,r,id,blk;}q[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline void Modify(int w, int t) {
for (int j=divs[w].size()-1,c;~j;j--) {
c = divs[w][j];
if (~t) ans += cnt, cnt += phi;
else cnt -= phi, ans -= cnt;
}
}
int main() {
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
n = read(); BLK = sqrt(n) + 1; phi[1] = 1;
for (int i=2;i<=n;i++) {
if (!vis[i]) phi[i] = i-1, pri[++tot] = i;
for (int j=1;j<=tot&&pri[j]*i<=n;j++) {
vis[i*pri[j]] = 1;
if (i % pri[j]) phi[i*pri[j]] = phi[i] * phi[pri[j]];
else {phi[i*pri[j]] = phi[i] * pri[j]; break;}
}
}
for (int i=1;i<=n;i++) {
arr[i] = read();
for (int j=i;j<=n;j+=i)
divs[j].push_back(i);
} m = read();
for (int i=1;i<=m;i++) {
q[i].l = read(); q[i].r = read();
q[i].id = i; q[i].blk = q[i].l / BLK;
}
sort(q+1, q+1+m, [](const Query &A, const Query &B){return A.blk<B.blk||(A.blk==B.blk&&A.r<B.r);});
for (int i=1,l=1,r=0;i<=m;i++) {
while (r > q[i].r) Modify(arr[r--], -1);
while (r < q[i].r) Modify(arr[++r], 1);
while (l > q[i].l) Modify(arr[--l], 1);
while (l < q[i].l) Modify(arr[l++], -1);
vout[q[i].id] = ans;
}
for (int i=1;i<=m;i++) printf("%lld\n",vout[i]);
return 0;
}
Heya i’m for the first time here. I found this board and
I find It really useful & it helped me out a lot. I hope to give something back and aid others like you aided me.
This article will assist the internet visitors for creating new weblog or even a weblog from start to end.
I’m curious to find out what blog platform you’re working with?
I’m experiencing some minor security problems with my latest blog and I would like to find something
more safe. Do you have any suggestions?
WOW just what I was looking for. Came here by searching for quest bars cheap
Hi there! I realize this is somewhat off-topic however I needed to ask.
Does operating a well-established website like yours take a large amount
of work? I’m completely new to operating a blog however I do
write in my journal every day. I’d like to start a blog so I can easily share my experience and views online.
Please let me know if you have any kind of ideas or tips for brand new aspiring bloggers.
Thankyou!
Link exchange is nothing else but it is simply placing the other person’s weblog link on your page at suitable place and other person will
also do similar for you.
Fantastic beat ! I wish to apprentice while you amend your web site, how
could i subscribe for a blog site? The account helped me
a acceptable deal. I had been a little bit acquainted
of this your broadcast provided bright clear idea
I am always looking online for articles that can benefit me. Thanks!
Hey are using WordPress for your blog platform?
I’m new to the blog world but I’m trying to get started and create my own. Do you need any html coding expertise to make your own blog?
Any help would be greatly appreciated!
Heya i am for the first time here. I came across this board
and I to find It truly helpful & it helped me out
much. I hope to provide something again and aid others such as you aided me.
Hello! Quick question that’s totally off topic. Do you know how
to make your site mobile friendly? My website looks weird when viewing from my iphone4.
I’m trying to find a theme or plugin that might be able to resolve this problem.
If you have any recommendations, please share. Many thanks!
hello there and thank you for your info – I’ve
certainly picked up anything new from right here. I did however expertise some technical issues using this website, since
I experienced to reload the web site lots of times previous
to I could get it to load properly. I had been wondering if
your web host is OK? Not that I am complaining, but sluggish loading instances times will often affect your placement in google and can damage your quality score if advertising and marketing with Adwords.
Anyway I am adding this RSS to my email and can look out for a lot more of your respective interesting content.
Make sure you update this again soon.
Howdy! Quick question that’s completely off topic. Do you
know how to make your site mobile friendly? My website looks weird when viewing from
my iphone. I’m trying to find a theme or plugin that
might be able to correct this problem. If you have any suggestions, please share.
Cheers!
I am genuinely thankful to the holder of this site who has shared this impressive paragraph at here.
This design is incredible! You certainly know
how to keep a reader amused. Between your wit and your videos, I was
almost moved to start my own blog (well, almost…HaHa!) Wonderful job.
I really loved what you had to say, and more than that, how
you presented it. Too cool!
Hi there to every single one, it’s really a nice for me to pay
a quick visit this web site, it consists of precious Information.
Hey! This is my first visit to your blog! We are a group of volunteers and
starting a new project in a community in the same niche.
Your blog provided us valuable information to work on. You have done a
outstanding job!
It’s awesome in support of me to have a web site,
which is valuable for my know-how. thanks admin
Please let me know if you’re looking for a writer for
your weblog. You have some really good articles and I feel I would be a good asset.
If you ever want to take some of the load off, I’d really like to write some material for your blog
in exchange for a link back to mine. Please send me an email if interested.
Thank you!
Incredible! This blog looks just like my old one! It’s on a entirely different subject but it has pretty much the same page layout and design. Great choice
of colors!
Great web site you have got here.. It’s difficult to find
high-quality writing like yours nowadays. I truly appreciate individuals like you!
Take care!!
This is my first time pay a quick visit at here and i am truly happy to read everthing
at single place.
Hello my friend! I want to say that this article is awesome, nice written and include almost all significant infos. I would like to see more posts like this.