川沙网站建设,资讯类网站建设资质要求,怎么做类似美团的网站,张家港外贸型网站制作Description 对于给出的n个询问#xff0c;每次求有多少个数对(x,y)#xff0c;满足a≤x≤b#xff0c;c≤y≤d#xff0c;且gcd(x,y) k#xff0c;gcd(x,y)函数为x和y的最大公约数。Input 第一行一个整数n#xff0c;接下来n行每行五个整数#xff0c;分别表示a、b、c…Description 对于给出的n个询问每次求有多少个数对(x,y)满足a≤x≤bc≤y≤d且gcd(x,y) kgcd(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 解题思路 和1101一样最后二维容斥一下就好了。 代码 #includecstdio
#includecstring
#includealgorithm
typedef long long lnt;
const int N50010;
int prime[N];
int miu[N];
lnt s[N];
bool vis[N];
int cnt;
int T;
void gtp(void)
{miu[1]1;for(int i2;iN;i){if(!vis[i]){prime[cnt]i;miu[i]-1;}for(int j1;jcntprime[j]*iN;j){vis[prime[j]*i]true;if(i%prime[j]0){miu[i*prime[j]]0;break;}miu[prime[j]*i]-miu[i];}}for(int i1;iN;i)s[i]s[i-1]miu[i];return ;
}
lnt query(lnt a,lnt b,lnt d)
{a/d;b/d;lnt cstd::min(a,b);lnt ans0;for(int k1,u;kc;ku1){ustd::min(a/(a/k),b/(b/k));ans(s[u]-s[k-1])*(a/k)*(b/k);}return ans;
}
int main()
{gtp();scanf(%d,T);while(T--){lnt a,b,c,d,k;scanf(%lld%lld%lld%lld%lld,a,b,c,d,k);a--,c--;lnt ansquery(b,d,k)query(a,c,k)-query(a,d,k)-query(b,c,k);printf(%lld\n,ans);}return 0;
} 转载于:https://www.cnblogs.com/blog-Dr-J/p/10161311.html
