hdu1695 GCD

hdu1695 GCD

​​ Problem Description Given 5 integers: a, b, c, d, k, you’re to find x in a…b, y in c…d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you’re only required to output the total number of different number pairs. Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same. Yoiu can assume that a = c = 1 in all test cases.

Input The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases. Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.

Output For each test case, print the number of choices. Use the format in the example.

Sample Input 2 1 3 1 5 1 1 11014 1 14409 9

Sample Output Case 1: 9 Case 2: 736427

Hint For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).

Source 2008 “Sunline Cup” National Invitational Contest

Recommend wangye | We have carefully selected several similar problems for you: 1689 1690 1693 1691 1698 注意去重即可

#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;bool not_prime[N];int prime[N],tot,T,mu[N],a,b,c,d,k;int main(){ freopen("hdu1695.in","r",stdin); mu[1]=1; for (int i=2;i<=1e5;++i){ if (!not_prime[i]) prime[++tot]=i,mu[i]=-1; for (int j=1;prime[j]*i<=1e5;++j){ not_prime[prime[j]*i]=1; if (i%prime[j]==0) {mu[prime[j]*i]=0;break;}else mu[prime[j]*i]=-mu[i]; } }for (int i=1;i<=1e5;++i) mu[i]+=mu[i-1]; T=read(); for (int cnt=1;cnt<=T;++cnt){ printf("Case %d: ",cnt); a=read();b=read();c=read();d=read();k=read(); if (k==0) {puts("0");continue;}b/=k;d/=k; if(b>d) swap(b,d);int last;ll ans=0; for (int i=1;i<=b;i=last+1){ last=min(d/(d/i),b/(b/i)); ans+=(ll)(mu[last]-mu[i-1])*(d/i)*(b/i); }ll ans1=0; for (int i=1;i<=b;i=last+1){ last=b/(b/i); ans1+=(ll)(mu[last]-mu[i-1])*(b/i)*(b/i); }ans-=ans1>>1; printf("%lld\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。