当前位置：网站首页>HDU 4135：Co-prime （容斥原理）

HDU 4135：Co-prime （容斥原理）

2022-08-10 11:08:00 【51CTO】

Co-prime

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

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

Sample Output

       
       Case #1: 5
       
Case #2: 10
      
1.
2.

思路：通常我们求1-ｎ中与ｎ互质的数的个数都是用欧拉函数！但如果ｎ比较大或者是求１～ｍ中与ｎ互质的数的个数等等问题，要想时间效率高的话还是用容斥原理！

容斥：先对n分解质因数，分别记录每个质因数，那么所求区间内与某个质因数不互质的个数就是n / r(i)，假设r(i)是r的某个质因子假设只有三个质因子，总的不互质的个数应该为p1+p2+p3-p1*p2-p1*p3-p2*p3+p1*p2*p3, 及容斥原理，可以转向百度百科查看相关内容 pi代表n/r(i),即与某个质因子不互质的数的个数，当有更多个质因子的时候，可以用状态压缩解决，二进制位上是1表示这个质因子被取进去了。如果有奇数个1，就相加，反之则相减。

AC代码：

       
       #include<stdio.h>
       
       #include<string.h>
       
       #include<iostream>
       
       #include<vector>
       
       typedef 
       
       __int64 
       
       LL;
       
       using 
       
       namespace 
       
       std;
       
       vector
       
       <
       
       LL
       
       >
       
       prime;
       
       void 
       
       jprime(
       
       LL 
       
       n)   
       
       //分解质因子
       
{
       
       for(
       
       LL 
       
       i
       
       =
       
       2; 
       
       i
       
       *
       
       i
       
       <=
       
       n; 
       
       i
       
       ++)
       
       if(
       
       n
       
       %
       
       i
       
       ==
       
       0)
       
        {
       
       prime.
       
       push_back(
       
       i); 
       
       //质因子
       
       while(
       
       n
       
       %
       
       i
       
       ==
       
       0)
       
       n
       
       /=
       
       i;
       
        }
       
       if(
       
       n
       
       >
       
       1)
       
       prime.
       
       push_back(
       
       n);
       
}
       
       LL 
       
       solve(
       
       LL 
       
       a,
       
       LL 
       
       b,
       
       LL 
       
       n)    
       
       //[a,b]中与n互质的数的个数
       
{
       
       LL 
       
       sum
       
       =
       
       0;
       
       LL 
       
       size
       
       =
       
       prime.
       
       size();
       
       for(
       
       LL 
       
       msk
       
       =
       
       1; 
       
       msk
       
       <(
       
       1
       
       <<
       
       size); 
       
       msk
       
       ++) 
       
       //共有2^size种组合情况
       
    {
       
       LL 
       
       mult
       
       =
       
       1,
       
       bits
       
       =
       
       0;
       
       for(
       
       LL 
       
       i
       
       =
       
       0; 
       
       i
       
       <
       
       size; 
       
       i
       
       ++)    
       
       //枚举每一种情况
       
        {
       
       if(
       
       msk
       
       &(
       
       1
       
       <<
       
       i))  
       
       //如果在当前判断之内
       
            {
       
       ++
       
       bits;
       
       mult
       
       *=
       
       prime[
       
       i];
       
            }
       
        }
       
       LL 
       
       cur
       
       =
       
       b
       
       /
       
       mult
       
       -(
       
       a
       
       -
       
       1)
       
       /
       
       mult;   
       
       //中间结果
       
       if(
       
       bits
       
       &
       
       1)
       
       sum
       
       +=
       
       cur;
       
       else 
       
       sum
       
       -=
       
       cur;
       
    }
       
       return 
       
       b
       
       -
       
       a
       
       -
       
       sum
       
       +
       
       1;
       
}
       
       int 
       
       main()
       
{
       
       LL 
       
       T;
       
       scanf(
       
       "%I64d",
       
       &
       
       T);
       
       for(
       
       LL 
       
       t
       
       =
       
       1; 
       
       t
       
       <=
       
       T; 
       
       t
       
       ++)
       
    {
       
       LL 
       
       a,
       
       b,
       
       n;
       
       scanf(
       
       "%I64d%I64d%I64d",
       
       &
       
       a,
       
       &
       
       b,
       
       &
       
       n);
       
       prime.
       
       clear();
       
       jprime(
       
       n);
       
       printf(
       
       "Case #%I64d: %I64d\n",
       
       t,
       
       solve(
       
       a,
       
       b,
       
       n));
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15746719/5562559

当前位置：网站首页>HDU 4135：Co-prime （容斥原理）

HDU 4135：Co-prime （容斥原理）

Co-prime

边栏推荐

猜你喜欢

随机推荐