HDU-4135 Co-prime(容斥原理)

野性酷女 2022-06-10 13:55 247阅读 0赞

Co-prime

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

题意：给你A，B，N，问在\[A,B\]中有多少数与N互质。

思路：与N互质也就是gcd(x,N)=1。那么我们可以把N分解成素因数，然后找在\[A,B\]中有多少这些素因数的倍数，然后再用容斥原理，奇加偶减，我们就可以把\[A,B\]中与N不互质的全部找出来，然后再用总数一减，就是答案。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100005;
    const int MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    int prime[MAXN], primesize;
    bool isprime[MAXN];
    void getlist(int listsize)
    {
    	memset(isprime, 1, sizeof(isprime));
    	isprime[1] = false;
    	for (int i = 2; i <= listsize; i++)
    	{
    		if (isprime[i])prime[++primesize] = i;
    		for (int j = 1; j <= primesize&&i*prime[j] <= listsize; j++)
    		{
    			isprime[i*prime[j]] = false;
    			if (i%prime[j] == 0)break;
    		}
    	}
    }
    
    int num[70];
    int vis[70];
    int t;
    LL ans;
    LL aa, bb, cc;
    void solve(int a)
    {
    	int k = a;
    	memset(num, 0, sizeof num);
    	t = 0;
    	for (int i = 1; prime[i]*prime[i]<=k; i++)
    	{
    		if(a%prime[i]==0)
    			num[++t] = prime[i];
    		while (a%prime[i]==0)
    		{
    			a /= prime[i];
    		}
    	}
    	if (a != 1)
    		num[++t] = a;
    }
    
    void solve2()
    {
    	int s = 0;
    	int res = 1;
    	for (int i = 1; i <= t; i++)
    	{
    		if (vis[i])
    		{
    			res *= num[i];
    			s++;
    		}
    	}
    	if (s % 2 == 1)
    		ans += bb / res - (aa - 1) / res;
    	else
    		ans-= bb / res - (aa - 1) / res;
    }
    
    int main()
    {
    	int T;
    	getlist(100003);
    	scanf("%d", &T);
    	for (int CAS = 1; CAS <= T; CAS++)
    	{
    		memset(vis, 0, sizeof vis);
    		ans = 0;
    		scanf("%lld%lld%lld", &aa, &bb, &cc);
    		solve(cc);
    		for (int i = 1; i < 1<<t; i++)
    		{
    			int tmp = i;
    			for (int j = 1; j <= t; j++)
    			{
    				vis[j] = tmp & 1;
    				tmp >>= 1;
    			}
    			solve2();
    		}
    		printf("Case #%d: %lld\n",CAS, bb-aa+1-ans);
    	}
    }