最不会的一集，题目一点看不懂
神YY虐完数论后给傻×kAc出了一题
给定\(N, M\),求\(1 \le x \le N, 1 \le y \le M\)且 \(\gcd(x, y)\) 为质数的 \((x, y)\) 有多少对
kAc这种傻×必然不会了，于是向你来请教
多组输入
先钦定 \(n \le m\)
考虑一个非常暴力的做法
\[\sum_{x=1}^N\sum_{y=1}^M[\gcd(x,y)\in primes]
\]
暴力是明显的\(\text O(nm)\)，略看\(n\)和\(m\)的值\(n,m\le 1e7\)肯定过不去
考虑枚举每个质数\(k\)
\[\sum_{k\in primes}\sum_{x=1}^{N}\sum_{y=1}^{M}[\gcd(x,y)=k]
\]
接着直接暴力除去\(k\)
\[\sum_{k\in primes}\sum_{x=1}^{\left \lfloor \frac{N}{k}\right \rfloor}\sum_{y=1}^{\left \lfloor \frac{M}{k}\right \rfloor}[\gcd(x,y)=1]
\]
然后这个式子貌似就稍微能看点了，然后突然发现用性质可以接着推然后冲冲冲
\[\sum_{k\in primes}\sum_{x=1}^{\left \lfloor \frac{N}{k}\right \rfloor}\sum_{y=1}^{\left \lfloor \frac{M}{k}\right \rfloor}\sum_{d|\gcd(x,y)}\mu(d)
\]
接着瞎推，想办法优化掉两个枚举\(x\)和\(y\)的那\(\sum\)
胡乱观察发现既然这里的\(d\)一定是\(\gcd(x,y)\)的倍数可以直接乘进去
\[\sum_{k\in primes}\ \sum^{\left \lfloor \frac{N}{k}\right \rfloor}_{d=1}\mu(d)\times \lfloor \frac{M}{k\times d}\rfloor\times \lfloor \frac{N}{k\times d}\rfloor
\]
然后复杂度还是过不去
破防了只好接着推式子，按理说这里的\(k\times d\)恐怕是可以枚举出来的，所以随便乱设一个\(t=kd\)
\[\sum_{k\in primes}\ \sum^{\left \lfloor \frac{N}{k}\right \rfloor}_{d=1}\mu(\frac tk)\times \lfloor \frac{M}{t}\rfloor\times \lfloor \frac{N}{t}\rfloor
\]
\[\sum_{t=1}^{N}\lfloor \frac{M}{t}\rfloor \lfloor \frac{N}{t}\rfloor\sum_{d|t}\mu(\frac td)
\]
然后一个乱七八糟的线性筛解决$$\sum_{d|t}\mu(\frac td)$$
然后前面的数论分块就行了
$\text {My Code}$
#include<bits/stdc++.h>
#define int long long
const int INF=0x66CCFF0712;
namespace IO{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen("data.in","r",stdin);freopen("data.out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0)putchar(F[--cnt]);}
}
#define close IO::close
#define Fire IO::Fire
#define read IO::read
#define write IO::write
#define cin std::cin
#define cout std::cout
#define endl '\n'
#define min(a,b) ((a)<(b))?(a):(b)
#define max(a,b) ((a)>(b))?(a):(b)
using namespace std;
const int N=1e7+5;
int tot,mu[N],g[N],sum[N],prime[N];
bool check[N];
signed main(){
mu[1]=1;
for(int i=2;i<=1e7;i++){
if(!check[i])
prime[++tot]=i,
mu[i]=-1,
g[i]=1;
for(int j=1;j<=tot&&i*prime[j]<=1e7;j++){
check[i*prime[j]]=1;
if(!(i%prime[j])){
mu[i*prime[j]]=0;
g[i*prime[j]]=mu[i];
break;
}
else
mu[i*prime[j]]=-mu[i],
g[i*prime[j]]=mu[i]-g[i];
}
}
for(int i=1;i<=1e7;i++)
sum[i]=sum[i-1]+g[i];
for(int i=read();i;i--){
int n=read(),m=read();
if(n>m) swap(n,m);
int ans=0,pos=INF;
for(int i=1;i<=n;i=pos+1){
pos=min(n/(n/i),m/(m/i));
ans+=(int)(n/i)*(m/i)*(sum[pos]-sum[i-1]);
}
write(ans);
puts("");
}
}
但是有个问题啊！虽然OJ上对了，但是洛谷上过不去为什么
先考虑一下卡常，首先换成FastIO，然后把一些不必要的数组换成int类型，接下来就过了
$\text{My Code}$
#include<bits/stdc++.h>
using namespace std;
namespace Fread{const int SIZE = (1 << 18);char buf[SIZE],*S,*T;inline char getchar() {if(S==T){T = (S = buf) + fread(buf,1,SIZE,stdin); if(S==T) return '\n';} return *S++;}}
namespace Fwrite {const int SIZE = (1 << 18);char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout), S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{ ~NTR() { flush(); }}ztr;}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
struct Reader{
template <typename T>
Reader&operator>>(T&x){char c=getchar();bool f=false;while (c<'0'||c>'9') { if(c == '-')f = true;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}if(f)x=-x;return *this;}
Reader&operator>>(double & x) {char c=getchar();short f=1,s=0;x=0;double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
Reader&operator>>(long double&x){char c=getchar();short f=1,s=0;x=0;long double t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}
Reader&operator>>(__float128&x){char c=getchar();short f=1,s=0;x=0;__float128 t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.') c = getchar();else return x*=f, *this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return *this;}
Reader&operator>>(char&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}
Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return *this;}
Reader&operator>>(string&str){char c=getchar();str.clear();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return *this;}
template<class _Tp>
Reader&operator>>(vector<_Tp>&vec){for(unsigned i=0;i<vec.size();i++)cin>>vec[i];return *this;}
template<class _Tp,class _tp>
Reader&operator>>(pair<_Tp,_tp>&a){cin>>a.first>>a.second;return *this;}
Reader(){}
}cin;
const char endl='\n';
struct Writer{
static const int set_precision = 6;
typedef int mxdouble;
template<typename T>
Writer&operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}
Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<set_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<set_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}
Writer&operator<<(char c){putchar(c);return*this;}
Writer& operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed) putchar(str[st++]);return *this;}
template<class _Tp>
Writer&operator<<(vector<_Tp>vec){for(unsigned i=0;i<vec.size()-1;i++)cout<<vec[i]<<" ";cout<<vec[vec.size()-1];return *this;}
template<class _Tp,class _tp>
Writer&operator<<(pair<_Tp,_tp>a){cout<<a.first<<" "<<a.second;return *this;}
Writer(){}
}cout;
}
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) < (b) ? (a) : (b))
/* --------------- fast io --------------- */
const int N=1e7+5;
int tot,mu[N],f[N],pri[N];
long long sum[N];
bool check[N];
signed main(){
// freopen("1.in","r",stdin);
// freopen("tmp.out","w",stdout);
mu[1]=1;
for(int i=2;i<=10000000;i++){
if(!check[i]){
pri[++tot]=i;
mu[i]=-1;
}
for(int j=1;j<=tot&&i*pri[j]<=10000000;j++) {
check[i*pri[j]]=1;
if (i%pri[j]==0) break;
mu[i*pri[j]]=-mu[i];
}
}
for(int i=1;i<=tot;i++)
for(int j=1;j*pri[i]<=10000000;j++)
f[pri[i]*j]+=mu[j];
for(int i=1;i<=10000000;i++)
sum[i]=sum[i-1]+f[i];
int q;
cin>>q;
for(int i=q;i;i--){
int n,m;
cin>>n>>m;
if(n>m) swap(n,m);
long long ans=0,pos=0;
for(int i=1;i<=n;i=pos+1){
pos=min(n/(n/i),m/(m/i));
ans+=(long long)(n/i)*(m/i)*(sum[pos]-sum[i-1]);
}
cout<<ans<<endl;
}
}
后记：就这点修改这能从3000ms优化到1600ms真的想不到
- 数表
有一张 \(n×m\) 的数表，其第 \(i\) 行第 \(j\) 列 \((1 \le i \le n,1 \le j \le m)\) 的数值为能同时整除 \(i\) 和 \(j\) 的所有自然数之和。
给定 \(a\)，计算数表中不大于 \(a\) 的数之和。
简化题意：求
\[{\sum_{i=1}^n\sum_{j=1}^m[\sum_{d|i且d|j}d\le a]\sum_{d|i且d|j}d}
\]
这个式子看起来就非常恶心，肯定要化掉一大堆\(\sum\)
定义
\[f(n)=\sum_{d|n}d
\]
那么上面的式子就是
\[{\sum_{i=1}^n\sum_{j=1}^m f(\gcd(i,j))\cdot[f(\gcd(1,j)\le a)]}
\]
发现这个\(a\)很烦人啊，所以尝试先不考虑\(a\)这个限制
那么式子就是
\[{\sum_{i=1}^n\sum_{j=1}^m f(\gcd(i,j))}
\]
稍微能看点了
接着和上题一样的思路：考虑枚举\(\gcd(i,j)\)的值
\[\sum_{k=1}^{\min(n,m)}f(k)\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=k]
\]
熟悉的上下同时拆掉\(k\)
\[\sum_{k=1}^{\min(n,m)}f(k)\sum_{i=1}^{\lfloor \frac nk\rfloor}\sum_{j=1}^{\lfloor \frac mk\rfloor} [\gcd(i,j)=1]
\]
用反演结论
\[\sum_{k=1}^{\min(n,m)}f(k)\sum_{i=1}^{\lfloor \frac nk\rfloor}\sum_{j=1}^{\lfloor \frac mk\rfloor} \sum_{d|\gcd(i,j)}\mu(d)
\]
大力拆\(\sum\)
\[\sum_{k=1}^{\min(n,m)}f(k)\sum_{d=1}^{\lfloor\frac{\min(n,m)}k\rfloor}\mu(d)\lfloor \frac n{kd}\rfloor\lfloor \frac m{kd}\rfloor
\]
诶好熟悉的感觉
设\(t=kd\)然后枚举\(t\)
\[\sum_{t=1}^{\min(n,m)}\lfloor \frac n{kd}\rfloor\lfloor \frac m{kd}\rfloor \sum_{k|t} f(k)\mu(\frac tk)
\]
熟悉多了，老样子前面整除分块，后面预处理就行
但是没考虑\(a\)，直接将询问按照\(a\)排序就行