题目链接:https://cn.vjudge.net/problem/Gym-101982B
题目大意: 给你(a,b)和(c,d)这两个区间,然后问你这两个区间中互素的对数是多少.
具体思路:和我上一篇写莫比乌斯入门的博客的思路一样,不过就是加了下限,原来的那一篇的下限是1,现在这一篇的下限是题目给的数.所以这一块就需要考虑到去重.
AC代码:
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<cstring>
#include<stdio.h>
using namespace std;
# define ll long long
# define inf 0x3f3f3f3f
const int maxn =10000000+100;
# define ll long long
ll mu[maxn];
ll vis[maxn];
ll prim[maxn];
void Get_mu(ll n)
{
mu[1]=1;
int cnt=0;
for(ll i=2; i<n; i++)
{
if(!vis[i])
{
prim[cnt++]=i;
mu[i]=-1;
}
for(ll j=0; j<cnt; j++)
{
ll k=i*prim[j];
if(k>n)break;
vis[k]=1;
if(i%prim[j])
{
mu[k]=-mu[i];
}
else
{
mu[k]=0;
break;
}
}
}
}
int main()
{
Get_mu(maxn);
int a,b,c,d;
cin>>a>>b>>c>>d;
ll ans=0;
if(b>d){
swap(a,c);
swap(b,d);
}// 注意如果交换的都需要交换.
for(int i=1; i<=b; i++)
{
ans+=mu[i]*(b/i)*(d/i);
}
for(int i=1; i<=a-1; i++)
{
ans-=mu[i]*((a-1)/i)*(d/i);
}
for(int i=1; i<=c-1; i++)
{
ans-=mu[i]*((c-1)/i)*(b/i);
}
int temp=min(a,c);
for(int i=1; i<=temp-1; i++)
{
ans+=mu[i]*((a-1)/i)*((c-1)/i);
}
cout<<ans<<endl;
return 0;
}