我这里在原题目上面加了扩充
修改：将改为x（x不是很大 ,其他题面内容不变
方法：首先将x分解质因子，变为 x=p1e1∗p2e2∗...∗pnenx=p_{1}^{e1}*p_{2}^{e2}*...*p_{n}^{en}x=p1e1∗p2e2∗...∗pnen的形式
在[a,b]区间我们枚举 %x的余数 i∈[0,x−1]i\in [0,x-1]i∈[0,x−1] ,.然后将 i 里x的质因子的数除掉，不够的乘起来，最后得到一个数y，相当于找到最小的y满足 i∗y%x=0i*y\%x = 0i∗y%x=0,则i对应的是[c,d]里y倍数的数量
单次询问时间复杂度：O(x∗xpri数量)O(x*x_{pri数量})O(x∗xpri数量)
将下面代码修改下可以过掉那题(文章最后面)。
代码如下
#include <bits/stdc++.h>#define LL long longconst int N = 2e5+5;using namespace std;int x,a,b,c,d;LL s1(int l,int r,int mo){//得到[l,r]里%x==mo的数量if(mo==0)mo=x;int ans=r/x - (l-1)/x;if(r%x>=mo)ans++;if((l-1)%x>=mo)ans--;return ans;}LL s2(int l,int r,int mo){//得到[l,r]为mo倍数的数量return r/mo-(l-1)/mo;}int pr[100][2],len;int main(){cin>>x>>a>>b>>c>>d;int lx=x;for(int i=2;i*i<=lx;i++)if(lx%i==0){pr[++len][0]=i;while(lx%i==0)pr[len][1]++,lx/=i;}if(lx!=1)pr[++len][0]=lx,pr[len][1]=1;LL ans=s1(a,b,0)*(d-c+1);//特判i=0for(int i=1;i<x;i++){int y=1,li=i;for(int j=1;j<=len;j++){int js=0;while(li%pr[j][0]==0)li/=pr[j][0],js++;if(js>=pr[j][1])js=0;else js=pr[j][1]-js;while(js--)y*=pr[j][0];}ans+=s1(a,b,i)*s2(c,d,y);}printf("%lld\n",ans);return 0;}/** 1 2 1 1 1 1 1000000000 1 1000000000*/
能AC这题的代码
#include <bits/stdc++.h>#define LL long longconst int N = 2e5+5;using namespace std;int x,a,b,c,d;LL s1(int l,int r,int mo){//得到[l,r]里%x==mo的数量if(mo==0)mo=x;int ans=r/x - (l-1)/x;if(r%x>=mo)ans++;if((l-1)%x>=mo)ans--;return ans;}LL s2(int l,int r,int mo){//得到[l,r]为mo倍数的数量return r/mo-(l-1)/mo;}int pr[100][2],len;int main(){x=;int lx=x;for(int i=2;i*i<=lx;i++)if(lx%i==0){pr[++len][0]=i;while(lx%i==0)pr[len][1]++,lx/=i;}if(lx!=1)pr[++len][0]=lx,pr[len][1]=1;while(cin>>a>>b>>c>>d){LL ans=s1(a,b,0)*(d-c+1);//特判i=0for(int i=1;i<x;i++){int y=1,li=i;for(int j=1;j<=len;j++){int js=0;while(li%pr[j][0]==0)li/=pr[j][0],js++;if(js>=pr[j][1])js=0;else js=pr[j][1]-js;while(js--)y*=pr[j][0];}// printf("y=%d\n",y);//printf("i=%d %d %d\n",i,y,s1(a,b,i)*s2(c,d,y));ans+=s1(a,b,i)*s2(c,d,y);}printf("%lld\n",ans);}return 0;}/***/
