找质因数..打素数表..DFS解容斥问题...

找质因数..打素数表..DFS解容斥问题...

Co-prime

Description

Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.

Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.

Input

The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 10 15) and (1 <=N <= 10 9).

Output

For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.

Sample Input

2

1 10 2

3 15 5

Sample Output

Case #1: 5

Case #2: 10

Hint

In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.

这题提醒的我就是在求一个数的质因数时..可以先将质数表打出来...10^9内的..质数表只需要扫到32000多(因为32000*32000>100000000了)...最终是打出3000多个质数..但要注意的是..有可能给的数就是质数..或者说有大于32000的质因数..但这样的质因数绝对最多一个...so...见程序.....

Program:

#include#define ll long longusing namespace std;ll a,b,n,t,T,x,s[31],M,N,ans,p;int Prime[40000];void DFS(ll i,ll w,ll k){ for (;i<=n;i++) { p=w*s[i]; M+=k*(N/p); DFS(i+1,p,-k); } return;}int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%I64d",&T); ll i,j,num=0; for (i=2;i<=33000;i++) { for (j=2;j*j<=i;j++) if (i%j==0) goto A; Prime[++num]=i; A: ; } for (t=1;t<=T;t++) { scanf("%I64d%I64d%I64d",&a,&b,&x); n=0; for (i=1;i<=num;i++) if (x%Prime[i]==0) { while (x%Prime[i]==0) x/=Prime[i]; s[++n]=Prime[i]; if (x==1) break; } if (x!=1) s[++n]=x; // 处理超过32000的质因数 a--; M=0; N=a; DFS(1,1,1); M=a-M; ans=M; M=0; N=b; DFS(1,1,1); M=b-M; ans=M-ans; printf("Case #%I64d: %I64d\n",t,ans); } return 0;}

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