Co-prime(容斥)

时间:2021-04-06 14:44:25

Co-prime

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2786    Accepted Submission(s): 1072

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

 

题解:模版题,刚开始开成int了;

代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
const int INF=0x3f3f3f3f;
typedef long long LL;
vector<int>p;
void getp(LL x){
p.clear();
for(int i=2;i*i<=x;i++){
if(x%i==0){
p.push_back(i);
while(x%i==0)x/=i;
}
}
if(x>1)p.push_back(x);
}
LL tc(LL x){
LL sum=0;
for(int i=1;i<(1<<p.size());i++){
LL num=0,cur=1;
for(int j=0;j<p.size();j++){
if(i&(1<<j)){
num++;
cur*=p[j];
}
}
if(num&1)sum+=x/cur;
else sum-=x/cur;
}
return x-sum;
}
int main(){
LL T,A,B,K,flot=0;
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld",&A,&B,&K);
getp(K);
printf("Case #%lld: %lld\n",++flot,tc(B)-tc(A-1));
}
return 0;
}