差分一下答案在进行统计，要分块并预处理出莫比乌斯函数的前缀和

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 #include
                
                 12 #define rep(i,l,r) for(int i=l;i<(r);i++)13 #define clr(a,x) memset(a,x,sizeof(a))14 using namespace std;15 typedef long long ll;16 typedef pair
                 
                   pii;17 #define mkp(a,b) make_pair(a,b)18 int readint(){19 int ans=0,f=1;20 char c=getchar();21 while(!isdigit(c)){22 if(c=='-') f=-1;23 c=getchar();24 }25 while(isdigit(c)){26 ans=ans*10+c-'0';27 c=getchar();28 }29 return ans*f;30 }31 const ll maxn=50009;32 ll n,cnt,a,b,c,d,k,mu[maxn],pri[maxn];33 bool p[maxn];34 void init(){35 mu[1]=1;36 rep(i,2,maxn){37 if(!p[i]){38 pri[cnt++]=i;mu[i]=-1;39 }40 rep(j,0,cnt){41 if(i*pri[j]>=maxn) break;42 p[i*pri[j]]=1;43 if(i%pri[j]) mu[i*pri[j]]=-mu[i];44 else{45 mu[i*pri[j]]=0;break;46 } 47 }48 }49 rep(i,2,maxn) mu[i]+=mu[i-1];50 }51 int f(int l,int r){52 l/=k;r/=k;53 if(l>r) swap(l,r);54 int ans=0;55 rep(L,1,l+1){56 int R=min(l/(l/L),r/(r/L));57 ans+=(mu[R]-mu[L-1])*(l/L)*(r/L);58 L=R;59 }60 return ans;61 }62 int main(){63 init();64 cin>>n;65 while(n--){66 a=readint();b=readint();c=readint();d=readint();k=readint();67 printf("%d\n",f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1));68 }69 return 0;70 }
                 
                
               
              
             
            
           
          
         
        
       
      

2301: [HAOI2011]Problem b

Time Limit: 50 Sec  Memory Limit: 256 MB

Submit: 2355  Solved: 996

[ ][ ][ ]

Description

 

对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。

Input

第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

 

Output

共n行，每行一个整数表示满足要求的数对(x,y)的个数

 

Sample Input

2

2 5 1 5 1

1 5 1 5 2

Sample Output

14

3

HINT

 

100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

 

Source

 

[ ][ ][ ]