数论-容斥原理 [L,R]内与N互质的数 HDU4135

题目大意：给定 A, B, 求 [A, B] 中与 N 互质的数的个数。

分解 N 的素因数 P[i]，考虑 [1, B] 中是 P[1] 倍数的数，是 P[2] 倍数的数...这些数的

交集是 [1, B] 中不与 N 互质的数（即与 N 有非 1 公约数的数）。

同理求 [1, A) 中不与 N 互质的数。前者减后者得到 t, 即 [A, B] 中不与 N 互质的数的数量。

答案是 B-A+1 - t.

1 <= A <= B <= 10¹⁵

1 <=N <= 10⁹

注意下 getans() 函数里二进制枚举子集（紫书里提到过）进行容斥原理计算的代码。

 1 #include <stdio.h>
 2 
 3 typedef long long LL;
 4 
 5 LL l, r, n, Pcnt;
 6 LL P[2000000];
 7 
 8 void div()
 9 {
10     Pcnt = 0;
11     LL v = n;
12     for (LL i = 2; i*i <= v; ++i) {
13         if (!(v % i)) P[++Pcnt] = i;
14         while (!(v % i)) v /= i;
15     }
16     if (v != 1) P[++Pcnt] = v;
17     return;
18 }
19 
20 LL getans(LL k)
21 {
22     LL ans = 0;
23     for (LL i = 1; i < (1<<Pcnt); ++i) {
24         LL v = 1, tot = 0;
25         for (LL j = 1; j <= Pcnt; ++j)
26             if ((i>>j-1) & 1) v *= P[j], tot ^= 1;
27         ans += k / v * (tot ? 1 : -1);
28     }
29     return ans;
30 }
31 
32 int main()
33 {
34     LL T, Ti;
35     scanf("%lld", &T);
36     for (Ti = 1; Ti <= T; ++Ti) {
37         scanf("%lld%lld%lld", &l, &r, &n);
38         div();
39         printf("Case #%lld: %lld
", Ti, r-l+1 - (getans(r)-getans(l-1)));
40     }
41     return 0;
42 }

View Code

题目: http://acm.hdu.edu.cn/showproblem.php?pid=4135

Co-prime

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

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¹⁵) and (1 <=N <= 10⁹).

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

Recommend

lcy | We have carefully selected several similar problems for you: 1796 1434 3460 1502 4136