p1518 Problem b
题目
https://www.luogu.org/problemnew/show/P2522
题解
莫比乌斯反演+容斥定理+整除分块。
参见 https://w...
p1518 Problem b
题目
https://www.luogu.org/problemnew/show/P2522
题解
莫比乌斯反演+容斥定理+整除分块。
参见 https://www.cnblogs.com/peng-ym/p/8647856.html
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=50010;
inline int read()
{
int f=1,num=0;
char ch=getchar();
while (!isdigit(ch)) { if (ch==\'-\') f=-1; ch=getchar(); }
while (isdigit(ch)) num=(num<<1)+(num<<3)+(ch^48), ch=getchar();
return num*f;
}
int num[maxn],vis[maxn],p[maxn],tot;
ll gcd(int a,int b,int k)
{
ll sum=0;
if (a>b) swap(a,b);
a/=k,b/=k;
for (int l=1,r;l<=a;l=r+1)
{
r=min(a/(a/l),b/(b/l));
sum+=(ll)(num[r]-num[l-1])*(a/l)*(b/l);
}
return sum;
}
int main()
{
num[1]=1;
for (int i=2;i<=maxn;++i)
{
if (!vis[i])
num[i]=-1,p[++tot]=i;
for (int j=1;j<=tot&&(ll)i*p[j]<=maxn;++j)
{
vis[i*p[j]]=1;
if(i%p[j]==0) break;
num[i*p[j]]=-num[i];
}
num[i]+=num[i-1];
}
int n=read();
while (n--)
{
int a=read(),b=read(),c=read(),d=read(),k=read();
ll ans=gcd(b,d,k)-gcd(b,c-1,k)-gcd(a-1,d,k)+gcd(a-1,c-1,k);
printf(\"%lld\\n\", ans);
}
return 0;
}
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
