[HDOJ4135]Co-prime

摘要:
Pid=4135,意思是:给出一个范围[a,b],然后给你一个数字n,然后找到这个范围[a、b]中n的质数。具体思想是计算[1,a]中n的非素数的数量和[1,b]中n非素数的数目,然后使用上限减去非素数的数,然后求差。首先分解n的素因子,然后使用一个变量的二进制来表示素因子中的数字1。当变量为偶数时,会将其相加,如果变量为奇数,则会将其减去,因为计算是重复的。

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

题意:给一个区间[a,b],再给你一个数n,求在这个区间[a,b]中与n互质的数的个数。

思路:这是一道数学题,如果数据范围不大的话可以直接套用欧拉函数,但是数据范围给得很大。所以用容斥原理来做。

具体思路就是计算[1,a]中与n非互质的数的个数以及[1,b]中与n非互质的数的个数,然后用上限减掉非互质的数的个数,之后作差即可。首先分解n的质因数,接着用一个变量的二进制表示质因数中1的数量,当这个变量是偶数的时候就加,奇数的话就减,因为重复计算了(详解见书《挑战程序设计竞赛P297》)。代码如下:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 vector<LL> v;
10 LL a, b;
11 LL n;
12 
13 void init() {
14     v.clear();
15     scanf("%I64d %I64d %I64d", &a, &b, &n);
16     LL nn = (LL)sqrt(n) + 1;
17     for(int i = 2; i < nn; i++) {
18         if(n % i == 0) {
19             v.push_back(i);
20             while(n % i == 0) {
21                 n /= i;
22             }
23         }
24     }
25     if(n > 1) {
26         v.push_back(n);
27     }
28 }
29 
30 LL solve(LL x, LL y) {
31     LL ans;
32     LL m ,cnt;
33     LL s = 1 << v.size();
34     for(int i = 1; i < s; i++) {
35         m = 1;
36         cnt = 0;
37         for(int j = 0; j < v.size(); j++) {
38             if(i & (1 << j)) {
39                 m *= v[j];
40                 cnt++;
41             }
42         }
43         if(cnt & 1) {
44             ans += x / m;
45         }
46         else {
47             ans -= x / m;
48         }
49     }
50     return x - ans;
51 }
52 int main() {
53     int t;
54     int kase = 1;
55     scanf("%d", &t);
56     while(t--) {
57         init();
58         LL l, r;
59         l = solve(a-1, n);
60         r = solve(b, n);
61         cout << "Case #" << kase++ << ": " << r - l << endl;
62     }
63 }

免责声明:文章转载自《[HDOJ4135]Co-prime》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇Linux进程管理命令[HDOJ5391]Zball in Tina Town下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

质因数分解

第一题 质因数分解 #include<bits/stdc++.h> using namespace std; int n,x,y; int main(){ cin>>n; for(int i=2;i<=n;i++) { if(n%i==0) { x=n/i; y=max(x,i); break; } } cout<<...

扩展卢卡斯学习笔记

前言 不知道为什么对这种名字前面带个“扩展”的算法一直抱有一种畏惧心理。。。 扩展卢卡斯的作用就是在不保证(p)是质数,求(C_n^m\% p)。 但由于复杂度还是对(p)有一定依赖,因此还是做不到任意模数。 质因数分解+(CRT)合并 考虑我们给(p)做一个质因数分解,拆成若干(p_i^{k_i})乘积的形式。 由于这些(p_i^{k_i})两两互质,以它...

问题 C: 质因数的个数

1947: 质因数的个数 时间限制: 1 Sec  内存限制: 32 MB提交: 245  解决: 114[提交][状态][讨论版][命题人:外部导入] 题目描述 求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。 输入 可能有多组测试数据,每组测试数据的输入是一个正整数N,(1&l...

poj1845 Sumdiv(算数基本定理,质因数分解)

poj 题意:求(a^b)的所有约数之和(mod9901)的值.((1<=a,b<=5*10^7)) 分析:根据算数基本定理(任何一个大于1的正整数都能唯一分解为有限个质数的乘积),把a分解质因数,表示为(p_1^{c_1}*p_2^{c_2}*...*p_n^{c_n}),再由算数基本定理的"约数和"推论可得,(a^b)的所有约数之和为((1+...

2.尾部的零

题目要求出阶乘尾部后有多少个0,其实就是问阶乘里面有多少个10.所以这个问题也就可以等效于问表示阶乘这个数的质因数分解总共有多少个2与5,而2的个数肯定比5的个数多,所以我们只需要求出有多少个5就行了。而质因数分解一个数里有多少个5可以用公式:(n/5+n/5/5+n/5/5/5+……)来进行计算。 很多博客都介绍了这种算法,但是没有讲解具体的计算原理(或许...

CodeForces 1103D. Professional layer

题目简述:给定$1 leq n leq 10^6$个正整数$1 leq a_i leq 10^{12}$,修改第$i$个正整数$a_i$的花费为$1 leq e_i leq 10^9$,以及正整数$1 leq k leq 10^{12}$。要求选出若干个正整数进行一次修改,使得修改后所有正整数的最大公约数等于$1$。修改操作为:对于正整数$a$,选择$a$的...