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;
}
HDU 4135:Co-prime(容斥+二进制拆分)的更多相关文章
-
HDU 4135 Co-prime(容斥:二进制解法)题解
题意:给出[a,b]区间内与n互质的个数 思路:如果n比较小,我们可以用欧拉函数解决,但是n有1e9.要求区间内互质,我们可以先求前缀内互质个数,即[1,b]内与n互质,求互质,可以转化为求不互质,也 ...
-
题解报告:hdu 4135 Co-prime(容斥定理入门)
Problem Description Given a number N, you are asked to count the number of integers between A and B ...
-
HDU 4135 Co-prime(容斥+数论)
Co-prime Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Su ...
-
C - Visible Trees HDU - 2841 -莫比乌斯函数-容斥
C - Visible Trees HDU - 2841 思路 :被挡住的那些点(x , y)肯定是 x 与 y不互质.能够由其他坐标的倍数表示,所以就转化成了求那些点 x,y互质 也就是在 1 - ...
-
HDU 5297 Y sequence 容斥 迭代
Y sequence 题目连接: http://acm.hdu.edu.cn/showproblem.php?pid=5297 Description Yellowstar likes integer ...
-
hdu 6053 trick gcd 容斥
http://acm.hdu.edu.cn/showproblem.php?pid=6053 题意:给定一个数组,我们定义一个新的数组b满足bi<ai 求满足gcd(b1,b2....bn)&g ...
-
HDU 4336 Card Collector(容斥)
题意:要收集n种卡片,每种卡片能收集到的概率位pi,求收集完这n种卡片的期望.其中sigma{pi} <=1; 思路:容斥原理.就是一加一减,那么如何算期望呢.如果用二进制表示,0表示未收集到, ...
-
HDU 3970 Harmonious Set 容斥欧拉函数
pid=3970">链接 题解:www.cygmasot.com/index.php/2015/08/17/hdu_3970 给定n 求连续整数[0,n), 中随意选一些数使得选出的 ...
-
[HDU4135]CO Prime(容斥)
也许更好的阅读体验 \(\mathcal{Description}\) \(t\)组询问,每次询问\(l,r,k\),问\([l,r]\)内有多少数与\(k\)互质 \(0<l<=r< ...
随机推荐
-
Apartment 2019:(1)创建墙体
墙体建模 The Walls 软件:SketchUp Pro 2017 墙体模型 建模过程: 一.导入图像并调整大小 导入公寓平面参考图/户型图(来自网络),导入为图像.连续三击鼠标左键,选中所有的几 ...
-
Makefile ------ 在Makefile中进行宏定义-D
在Makefile中我们可以通过宏定义来控制源程序的编译.只要在Makefile中的CFLAGS(变量名随意)中通过选项-D来指定你于定义的宏即可. 如:CFLAGS += -D _YUQIANG在编 ...
-
Selenium Webdriver弹出框的种种类型
普通弹出框 div 一般这种 弹出框都属于dom的一部分,我们查看一下页面源码就可以定位到改弹出框了,然后定位下右上角的那个关闭, 这里有id,所以很方便通过 dr.findElement(By.id ...
-
在eclipse-oxygen-sts中,关于快捷键[CTRL + SHIFT + O]失效的问题
这是sts的一个bug,没关系,重新设置接口 按照如图位置修改即可 下图截自于*
-
Quartz定时任务和IIS程序池闲置超时时间冲突解决方案
一.问题描述 Bs项目中用Quartz功能执行一个定时任务(每隔5分钟执行一个Job),正常情况,Quartz定时任务会5分钟执行一次,但IIS程序池闲置 超时默认为20分钟,造成的结果是:定时任务只 ...
-
java IO字节流
字节流可以读取 复制 各种类型 的文件. 写文件 第一种:读文件,每次读取1024字节的内容,读取太大文件不会导致内存溢出 第二种:读文件,更简单 思考?如果复制一个电影 或 1G 以上的文件,会出现 ...
-
STL-set and multiset
! ! ! ! set 中的元素总是保持单调递增. set<int> a; set的插入 set没有尾部插入函数push_back(),元素的插入一般使用insert进行动态检索插入. a ...
-
nginx反向代理proxy_set_header自定义header头无效
公司使用nginx作为负载均衡,有时候需要自定义header头发送给后端的真实服务器. 想过去应该是非常的简单的事情. 例子如下: 设置代理服务器ip头 1 proxy_set_header X- ...
-
LintCode-35.翻转链表
翻转链表 翻转一个链表 样例 给出一个链表 1->2->3->null ,这个翻转后的链表为 3->2->1->null 挑战 在原地一次翻转完成 标签 链表 优步 ...
-
【循环节】 Codeforces Round #401 (Div. 2) A. Shell Game
容易发现存在循环节. #include<cstdio> using namespace std; int n,x,a[3][6]={{0,1,2,2,1,0},{1,0,0,1,2,2}, ...