首页 > 代码库 > HDU 4135 Co-prime(组合+容斥)
HDU 4135 Co-prime(组合+容斥)
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.
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: 10HintIn the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.
题意:求出[l,r]中n的互素数个数。
容斥+组合:1:我们求出n的所有素因数,然后求出[l,r]之间不互素的数个数s,n-s即答案。
2:n的m个素因数,考虑组合1~(1<<m)-1,容斥可得s.即不互素的数目。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<string> #include<iostream> #include<queue> #include<cmath> #include<map> #include<stack> #include<bitset> using namespace std; #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define CLEAR( a , x ) memset ( a , x , sizeof a ) typedef long long LL; typedef pair<int,int>pil; const int mod = 1000000007; LL a,b,n; int t; LL solve(LL r,LL n) { vector<int>v; for(int i=2;i*i<=n;i++) { if(n&&n%i==0) { v.push_back(i); while(n&&n%i==0) n/=i; } } if(n>1) v.push_back(n); LL sum=0; for(int t=1;t<(1<<v.size());t++) { LL mul=1,bits=0; for(int i=0;i<(int)v.size();i++) { if(t&(1<<i)) { ++bits; mul*=v[i]; } } if(bits&1) sum+=r/mul; else sum-=r/mul; } return r-sum; } int main() { int cas=1; scanf("%d",&t); while(t--) { scanf("%I64d%I64d%I64d",&a,&b,&n); printf("Case #%d: %I64d\n",cas++,solve(b,n)-solve(a-1,n)); } return 0; }
HDU 4135 Co-prime(组合+容斥)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。