网站dns,企业网站建设合同范本免费,长治网站运营,宁波网页开发哪家好【题目描述】 HYSBZ - 1101 【题目分析】 昨天测试出了一道差不多的题目#xff0c;我只能想到暴力#xff0c;各种优化#xff0c;最后都是运行了好久TLE#xff0c;最后才知道要用到莫比乌斯反演#xff0c;就想着今天研究一下#xff0c;得出的结论就是#xff0c;我…【题目描述】 HYSBZ - 1101 【题目分析】 昨天测试出了一道差不多的题目我只能想到暴力各种优化最后都是运行了好久TLE最后才知道要用到莫比乌斯反演就想着今天研究一下得出的结论就是我可能研究不来。。。 //要用到数论的知识我连人家的基本的定义都理解不了更不要说证明了。现在只能说学会用吧我知道这里的莫比乌斯反演可以快速求出[1,n]和[1,m]中所有互质的数字的数目当作板子用了吧。
这两天研究了一下数论函数回来再看这道入门题觉得。。。 学习了一下除法分块具体的那个推导我还是没有理解但是大概知道怎么用了。
首先因为要求的是gcd(x,y)d的我们就要想到转换成互质来做很多都是这样因为互质有很多性质有很多函数我们可以进行处理即求所有的gcd(x,y)1其中1xa/d,1yb/d关于等于1的等式我们要联想到元函数然后进行用莫比乌斯函数和恒等函数卷积展开就是著名的莫比乌斯反演其实只是卷积中很简单的一种。再根据和式的性质求的是所有能够整除gcd(i,j)1ia/d,1jb/d的数字k的莫比乌斯函数和我们从k的角度来看对于每一个k能够同时被他整除的个数为(a/d/k) * (b/d/k)而且k的取值范围是1kmin(a/d,b/d),所以我们将式子的形式改变一下就得到对k进行求和的式子然后用除法分块处理最后的时间复杂度应该是O(sqrt(n))
自己实现了一下直接A了。 【AC代码】
#includecstdio
#includecstring
#includecmath
#includeclimits#includealgorithmusing namespace std;typedef long long ll;int a,b,k;
int ans;
const int MAXN50005;
const int MAXM10005;
int prime[MAXN5];
int check[MAXN5];
int mobi[MAXN5];
int sum[MAXN5];
int tot0;void creat_prime()
{mobi[1]1;for(int i2;iMAXN;i){if(check[i]0){prime[tot]i;mobi[i]-1; }for(int j0;jtotprime[j]*iMAXN;j){check[prime[j]*i]1;if(i%prime[j]0){mobi[prime[j]*i]0;break;}else{mobi[prime[j]*i]-mobi[i];}}}for(int i1;iMAXN;i){sum[i]sum[i-1]mobi[i];}
}int solve(int n,int m)
{n/k; m/k;if(nm) swap(n,m); if(n0) return 0;int next,next1,next2;int tot0;for(int i1;in;inext){next1n/(n/i); next2m/(m/i);nextmin(next1,next2);tot(n/i)*(m/i)*(sum[next]-sum[i-1]);next;}return tot;
}int main()
{creat_prime();//check[2]1;int T,u,v,w,flag;scanf(%d,T);while(T--){ans0;scanf(%d%d%d,a,b,k);anssolve(a,b);//这里有可能需要用容斥来计算其他区间的互质的数目比如如果计算的是[a,b]和[c,d]那么anssolve(b,d)-solve(a-1,d)-solve(b,c-1)solve(a-1,c-1);printf(%d\n,ans);}return 0;
}自己实现的代码
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includeiostream
#includecmath
#includectime
#includeclimits
#includequeue
#includevector
#includeset
#includemap
using namespace std;typedef long long ll;
const int INF0x3f3f3f3f;
const int MAXN5e45;int prime[MAXN],mobius[MAXN],sum[MAXN];
bool check[MAXN];
int tot;void pre()
{tot0; mobius[1]1; sum[1]1;for(int i2;iMAXN;i){if(!check[i]){prime[tot]i; mobius[i]-1;}for(int j0;jtot prime[j]*iMAXN;j){check[prime[j]*i]true;if(i%prime[j]) mobius[prime[j]*i]-mobius[i];else{mobius[prime[j]*i]0; break;}}sum[i]sum[i-1]mobius[i];}
}int main()
{pre();int T; int a,b,d;scanf(%d,T);while(T--){int ans0;scanf(%d%d%d,a,b,d);a/d; b/d;int l,r;int limitmin(a,b);for(l1;llimit;lr1){rmin(a/(a/l),b/(b/l));ans(sum[r]-sum[l-1])*(a/l)*(b/l);}printf(%d\n,ans);}return 0;
}
