传送门: https://www.luogu.org/problemnew/show/P2522
- #include <cstdio>
- #include <cstring>
- #include <string>
- #include <cmath>
- using namespace std;
- #define ll long long
- #define re register
- const int N=5e4+10;
- const int M=5e4;
- inline void read(int &a)
- {
- a=0;
- int d=1;
- char ch;
- while(ch=getchar(),ch>'9'||ch<'0')
- if(ch=='-')
- d=-1;
- a=ch^48;
- while(ch=getchar(),ch>='0'&&ch<='9')
- a=(a<<3)+(a<<1)+(ch^48);
- a*=d;
- }
- int pri[N],cnt;
- ll mu[N];
- bool vis[N];
- inline void init()
- {
- mu[1]=1;
- for(re int i=2;i<=M;i++)
- {
- if(!vis[i])
- pri[++cnt]=i,mu[i]=-1;
- for(re int j=1;j<=cnt&&i*pri[j]<=M;j++)
- {
- vis[i*pri[j]]=1;
- if(i%pri[j]==0)
- break;
- mu[i*pri[j]]=-mu[i];
- }
- }
- for(re int i=1;i<=M;i++)
- mu[i]+=mu[i-1];
- }
- ll solve(int n,int m,int k)
- {
- ll ans=0;
- if(n>m)
- swap(n,m);
- n/=k;
- m/=k;
- for(int l=1,r;l<=n;l=r+1)
- {
- r=min(n/(n/l),m/(m/l));
- ans+=(mu[r]-mu[l-1])*(n/l)*(m/l);
- }
- return ans;
- }
- int main()
- {
- init();
- int T;
- read(T);
- while(T--)
- {
- int a,b,c,d,k;
- read(a);
- read(b);
- read(c);
- read(d);
- read(k);
- if(k==0)
- {
- printf("0\n");
- continue;
- }
- printf("%lld\n",solve(b,d,k)-solve(b,c-1,k)-solve(a-1,d,k)+solve(a-1,c-1,k));
- }
- return 0;
- }
- GCD2
来源: http://www.bubuko.com/infodetail-3074113.html