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

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

AC代码

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <set>

#include <string>

#define ll long long

#define ms(a) memset(a,0,sizeof(a))

#define pi acos(-1.0)

#define INF 0x3f3f3f3f

const 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<int,int>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<<k);i++)

		{

			int cnt=0;

			ll tmp=1;

			for(int j=0;j<k;j++)

			{

				if(i>>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;

}