Co-prime

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 6869 Accepted Submission(s): 2710

Problem 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 <= 1015) and (1 <=N <= 109).

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

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}.

题意

给出三个数a,b,n，求区间[a.b]中有多少和n互质的数

思路

先把n的质因子记录下来，然后利用容斥+二进制拆分分解求出1~（a-1）和1~b之间的与n互质的个数ans1和ans2，然后减去区间中数的个数减去（ans2-ans1）即可

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define ll long long#define ms(a) memset(a,0,sizeof(a))#define pi acos(-1.0)#define INF 0x3f3f3f3fconst double E=exp(1);const int maxn=1e6+10;using namespace std;int A[maxn];//用来存放质因子ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}ll lcm(ll a,ll b){ return a/gcd(a,b)*b;}int main(int argc, char const *argv[]){ int t; ll a,b,n; scanf("%d",&t); int x=0; while(t--) { ll ans1,ans; ans=ans1=0; map
                
                 mmp;//记录质因子是否出现过 scanf("%lld%lld%lld",&a,&b,&n); ll m=n; int k=0; for(int i=2;i*i<=m;i++) { if(m%i==0) { while(m%i==0) { if(mmp[i]==0) { A[k++]=i; mmp[i]=1; } m/=i; } } } if(m>1) { A[k++]=m; mmp[m]=1; } for(int i=1;i<(1<
                 
                  >j&1) { cnt++; tmp=lcm(tmp,A[j]); } } if(cnt&1) { ans+=(a-1)/tmp; ans1+=(b)/tmp; } else { ans-=(a-1)/tmp; ans1-=b/tmp; } } printf("Case #%d: %lld\n",++x,(b-a+1)-ans1+ans); } return 0;}

转载于:https://www.cnblogs.com/Friends-A/p/10324443.html

你可能感兴趣的文章