Co-prime
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1111 Accepted Submission(s): 405
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 <= 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}.
Source The Third Lebanese Collegiate Programming Contest
解題報告:簡單來說就是求區間[a, b]中于n互為素數的數的個數。我們知道如果求區間[1, n]與n互為素數的數的個數,可以使用歐拉定理。但是本題中無法使用。
不過可以簡單轉化一下,題目就是求[1, b]中互素的個數減去[1, a-1]中互素的個數。此時我們可以使用容斥原理。
即[1, b]中與2互為約數的數共有b/2個,與3互為約數的數的個數有b/3個。同時與2,3互為約數的數的個數就是b/2+b/3-b/lcm(2,3)。
把n因式分解分解。簡單計算可以知道,前10個素數相乘大于6*10^10,n的範圍是10^9,也就是說n的素數因子不超過10個。那麼複雜度就不會超過2^10*10。完全可以接受。
代碼如下:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int prime[30];
int top;
int cas;
LL co_prime(LL val)
{
LL ans = 0;
for (int i = 1; i < (1 << top); i++)
{
LL tmp = 1, flag = 0;
for (int j = 0; j < top; j++) if (i&(1 << j))
tmp *= prime[j], flag++;
if (flag & 1)
ans += val / tmp;
else
ans -= val / tmp;
}
return val - ans;
}
void work()
{
LL a, b;
int n;
scanf("%I64d%I64d%d", &a, &b, &n);
top = 0;
for (int i = 2; i*i <= n; i++) if (n%i==0)
{
prime[top++] = i;
while (n%i == 0) n /= i;
}
if (n > 1)
prime[top++] = n;
printf("Case #%d: %I64d\n", ++cas, co_prime(b) - co_prime(a-1));
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
work();
}