新视野OJ 2301 [HAOI2011]Problem b （数论-gcd） - c++编程基础

题意：对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k。

题解：和前几道题差不多，就是xy不是从1开始了，所以我们很容易联想到容斥原理，ans=gcd(b,d)-gcd(a-1,d)-gcd(b,c-1)+gcd(a-1,b-1)。

AC代码：

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
using namespace std;  
  
#define si1(a) scanf("%d",&a)  
#define si2(a,b) scanf("%d%d",&a,&b)  
#define sd1(a) scanf("%lf",&a)  
#define sd2(a,b) scanf("%lf%lf",&a,&b)  
#define ss1(s)  scanf("%s",s)  
#define pi1(a)    printf("%d\n",a)  
#define pi2(a,b)  printf("%d %d\n",a,b)  
#define mset(a,b)   memset(a,b,sizeof(a))  
#define forb(i,a,b)   for(int i=a;im) swap(n,m);  
    n/=k;   m/=k;  
  
    LL sum=0;  
    for(LL i=n;i>=1;i--)  
    {  
        f[i]=(n/i)*(m/i);  
        for(LL j=i+i;j<=n;j+=i)  
            f[i]-=f[j];  
    }  
    return f[1];  
}  
  
int main()  
{  
//    freopen("input.txt","r",stdin);  
    LL a,b,c,d;  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        //scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);  
        cin>>a>>b>>c>>d>>k;  
  
        if(a>b||c>d)  
        {  
            puts("0");  
            continue;  
        }  
        cout<

#include 




  
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
using namespace std;  
  
#define si1(a) scanf("%d",&a)  
#define si2(a,b) scanf("%d%d",&a,&b)  
#define sd1(a) scanf("%lf",&a)  
#define sd2(a,b) scanf("%lf%lf",&a,&b)  
#define ss1(s)  scanf("%s",s)  
#define pi1(a)    printf("%d\n",a)  
#define pi2(a,b)  printf("%d %d\n",a,b)  
#define mset(a,b)   memset(a,b,sizeof(a))  
#define forb(i,a,b)   for(int i=a;im) swap(n,m);  
    for(LL i=1,last=0;i<=n;i=last+1)  
    {  
        last=min(n/(n/i),m/(m/i));  
        res+=(sum[last]-sum[i-1])*(n/i)*(m/i);  
    }  
    return res;  
}  
  
int main()  
{  
//    freopen("input.txt","r",stdin);  
    GetPrimes();  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        scanf("%lld%lld%lld%lld%lld",&A,&B,&C,&D,&K);  
        LL ans=0;  
        ans+=Process(B/K,D/K);  
        ans-=Process((A-1)/K,D/K);  
        ans-=Process(B/K,(C-1)/K);  
        ans+=Process((A-1)/K,(C-1)/K);  
        printf("%lld\n",ans);  
    }  
}