相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3994
数据生成器：http://paste.ubuntu.com/23992676/
神犇题解：https://blog.sengxian.com/solutions/bzoj-3994
解题报告
这题要用到一个结论： $d(xy) = \sum\limits_{i|x} {\sum\limits_{j|y} {[\gcd (i,j) = 1]} } $
这个结论似乎没有办法从意义上去推导，证明也只能是展开后发现刚好相等
但这个结论前不久集训的时候就考过一次，然而做这题的时候一点印象都没有
我要是下一次还记不住这个结论就直播吃键盘！
好了现在开始说正解
知道上面的结论以后，答案就成了 $\sum\limits_{k = 1}^n {\mu (k)\sum\limits_{i = 1}^{\frac{n}{k}} {d(i)\sum\limits_{j = 1}^{\frac{m}{k}} {d(j)} } } $
然后设$f(i)$为除数函数的前缀和，答案就变成了： $\sum\limits_{k = 1}^n {\mu (k)f(\frac{n}{k})f(\frac{m}{k})} $
于是直接下底函数分块就可以啦！
Code
除数函数可以线筛，不过偷懒写的欧拉筛法
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 50000+9;
int n,m,tot,pri[N],mu[N],d[N],sum[N],f[N];
bool vis[N]; LL vout;
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 prework() {
mu[1] = 1;
for (int i=2;i<N;i++) {
if (!vis[i]) pri[++tot] = i, mu[i] = -1;
for (int j=1;j<=tot&&pri[j]*i<N;j++) {
vis[i*pri[j]] = 1;
if (i % pri[j]) mu[i*pri[j]] = -mu[i];
else {mu[i*pri[j]] = 0; break;}
}
}
for (int i=1;i<N;i++)
for (int j=i;j<N;j+=i)
d[j]++;
for (int i=1;i<N;i++) {
f[i] = f[i-1] + d[i];
sum[i] = sum[i-1] + mu[i];
}
}
int main() {
prework();
for (int T=read();T;T--,vout=0) {
n = read(); m = read();
if (m > n) swap(n, m);
for (int l=1,r;l<=m;l=r+1) {
r = min(n / (n / l), m / (m / l));
vout += (LL)(sum[r] - sum[l-1]) * f[n/l] * f[m/l];
}
printf("%lld\n",vout);
}
return 0;
}
Very neat blog.Really looking forward to read more. Awesome.
I know this site presents quality depending articles
or reviews and additional data, is there any other website
which gives these kinds of information in quality?
Hi there just wanted to give you a quick heads up and let
you know a few of the images aren’t loading properly. I’m not sure why but I think its
a linking issue. I’ve tried it in two different web browsers
and both show the same results.
Ridiculous quest there. What happened after?
Take care!
If you desire to obtain a great deal from this post then you have to apply such methods to your won weblog.
Heya i’m for the first time here. I found this board and I find It truly useful &
it helped me out much. I hope to give something back and help others like you
aided me.
Thanks for another informative blog. The place else may just I am getting that type of info written in such an ideal way?
I have a venture that I’m simply now running on, and I have been on the look out for such
information.
Hi everyone, it’s my first pay a visit at this site, and paragraph
is in fact fruitful in favor of me, keep up posting these articles.
I loved as much as you will receive carried out right
here. The sketch is attractive, your authored subject matter stylish.
nonetheless, you command get bought an nervousness over that you wish be delivering the following.
unwell unquestionably come further formerly again as exactly the same nearly very often inside case you shield
this increase.
Hello there, You have done a fantastic job. I’ll certainly digg it and personally suggest to my friends.
I am confident they will be benefited from this web site.
Good day! This is my first comment here so I just wanted to give a quick shout
out and say I genuinely enjoy reading your articles.
Can you suggest any other blogs/websites/forums that cover the same topics?
Thank you so much!
Good post. I learn something new and challenging on websites I stumbleupon every day.
It’s always interesting to read through articles from other authors and use a little something from their websites.
I’m curious to find out what blog platform you happen to be utilizing?
I’m having some small security problems with my
latest blog and I’d like to find something more
risk-free. Do you have any recommendations?
I don’t even know how I stopped up right here, however I believed
this submit used to be good. I do not recognise who you are but definitely you are going to a
famous blogger should you aren’t already. Cheers!
Thank you for sharing your info. I truly appreciate your efforts
and I will be waiting for your further post thanks once again.
Hi Dear, are you truly visiting this web page daily, if so then you
will without doubt obtain fastidious experience.
Howdy! This is my first visit to your blog! We are a collection 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 extraordinary job!
Today, while I was at work, my cousin stole my iphone and tested to see if it can survive a 30 foot drop, just so she can be a youtube sensation. My iPad is now destroyed and she has 83 views. I know this is completely off topic but I had to share it with someone!
I pay a quick visit everyday some blogs and blogs to
read articles or reviews, however this web site offers quality based content.
Spot on with this write-up, I truly think this site needs much more attention. I’ll probably be back
again to read through more, thanks for the information!
Excellent post but I was wondering if you could write a litte more on this topic?
I’d be very grateful if you could elaborate a little bit more.
Kudos!
Hey! I’m at work surfing around your blog from my new iphone!
Just wanted to say I love reading through your blog and look forward to all your posts!
Carry on the outstanding work!
Wonderful blog! I found it while browsing on Yahoo News. Do you
have any suggestions on how to get listed in Yahoo
News? I’ve been trying for a while but I never seem to get
there! Appreciate it
Spot on with this write-up, I actually think
this website needs a lot more attention. I’ll probably be back again to read more, thanks for the
info!
My brother recommended I might like this web site. He was
entirely right. This post actually made my day. You can not imagine simply
how much time I had spent for this info! Thanks!
It’s a pity you don’t have a donate button! I’d most
certainly donate to this fantastic blog! I guess for now i’ll
settle for bookmarking and adding your RSS feed to my Google account.
I look forward to fresh updates and will share this blog with my Facebook group.
Talk soon!
Thank you for every other informative site. The place else could I am getting that type of info written in such an ideal approach?
I have a mission that I’m just now working on, and I’ve been at the look out for such info.
Wonderful beat ! I wish to apprentice while you amend your website, how could i subscribe for a blog site?
The account aided me a acceptable deal. I had been tiny bit acquainted of this your broadcast provided bright clear
idea
This paragraph is really a nice one it assists new internet
visitors, who are wishing for blogging.
These are actually great ideas in about blogging.
You have touched some good points here. Any way keep up wrinting.
When I originally commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get three e-mails with the same comment. Is there any way you can remove people from that service? Thank you!
Keep on writing, great job!
It’s hard to come by experienced people about this topic, however, you
seem like you know what you’re talking about! Thanks
I think this is a real great blog article.Really thank you! Will read on…