HDU 4135:Co-prime(容斥+二进制拆分)

时间:2022-10-01 20:06:04

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}.

HDU 4135:Co-prime(容斥+二进制拆分)

题意

给出三个数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(容斥+二进制拆分)的更多相关文章

  1. HDU 4135 Co-prime(容斥:二进制解法)题解

    题意:给出[a,b]区间内与n互质的个数 思路:如果n比较小,我们可以用欧拉函数解决,但是n有1e9.要求区间内互质,我们可以先求前缀内互质个数,即[1,b]内与n互质,求互质,可以转化为求不互质,也 ...

  2. 题解报告:hdu 4135 Co-prime(容斥定理入门)

    Problem Description Given a number N, you are asked to count the number of integers between A and B ...

  3. HDU 4135 Co-prime(容斥&plus;数论)

    Co-prime Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Su ...

  4. C - Visible Trees HDU - 2841 -莫比乌斯函数-容斥

    C - Visible Trees HDU - 2841 思路 :被挡住的那些点(x , y)肯定是 x 与 y不互质.能够由其他坐标的倍数表示,所以就转化成了求那些点 x,y互质 也就是在 1 - ...

  5. HDU 5297 Y sequence 容斥 迭代

    Y sequence 题目连接: http://acm.hdu.edu.cn/showproblem.php?pid=5297 Description Yellowstar likes integer ...

  6. hdu 6053 trick gcd 容斥

    http://acm.hdu.edu.cn/showproblem.php?pid=6053 题意:给定一个数组,我们定义一个新的数组b满足bi<ai 求满足gcd(b1,b2....bn)&g ...

  7. HDU 4336 Card Collector&lpar;容斥&rpar;

    题意:要收集n种卡片,每种卡片能收集到的概率位pi,求收集完这n种卡片的期望.其中sigma{pi} <=1; 思路:容斥原理.就是一加一减,那么如何算期望呢.如果用二进制表示,0表示未收集到, ...

  8. HDU 3970 Harmonious Set 容斥欧拉函数

    pid=3970">链接 题解:www.cygmasot.com/index.php/2015/08/17/hdu_3970 给定n  求连续整数[0,n), 中随意选一些数使得选出的 ...

  9. &lbrack;HDU4135&rsqb;CO Prime&lpar;容斥&rpar;

    也许更好的阅读体验 \(\mathcal{Description}\) \(t\)组询问,每次询问\(l,r,k\),问\([l,r]\)内有多少数与\(k\)互质 \(0<l<=r&lt ...

随机推荐

  1. Apartment 2019:(1)创建墙体

    墙体建模 The Walls 软件:SketchUp Pro 2017 墙体模型 建模过程: 一.导入图像并调整大小 导入公寓平面参考图/户型图(来自网络),导入为图像.连续三击鼠标左键,选中所有的几 ...

  2. Makefile ------ 在Makefile中进行宏定义-D

    在Makefile中我们可以通过宏定义来控制源程序的编译.只要在Makefile中的CFLAGS(变量名随意)中通过选项-D来指定你于定义的宏即可. 如:CFLAGS += -D _YUQIANG在编 ...

  3. Selenium Webdriver弹出框的种种类型

    普通弹出框 div 一般这种 弹出框都属于dom的一部分,我们查看一下页面源码就可以定位到改弹出框了,然后定位下右上角的那个关闭, 这里有id,所以很方便通过 dr.findElement(By.id ...

  4. 在eclipse-oxygen-sts中,关于快捷键&lbrack;CTRL &plus; SHIFT &plus; O&rsqb;失效的问题

    这是sts的一个bug,没关系,重新设置接口 按照如图位置修改即可 下图截自于*

  5. Quartz定时任务和IIS程序池闲置超时时间冲突解决方案

    一.问题描述 Bs项目中用Quartz功能执行一个定时任务(每隔5分钟执行一个Job),正常情况,Quartz定时任务会5分钟执行一次,但IIS程序池闲置 超时默认为20分钟,造成的结果是:定时任务只 ...

  6. java IO字节流

    字节流可以读取 复制 各种类型 的文件. 写文件 第一种:读文件,每次读取1024字节的内容,读取太大文件不会导致内存溢出 第二种:读文件,更简单 思考?如果复制一个电影 或 1G 以上的文件,会出现 ...

  7. STL-set and multiset

    ! ! ! ! set 中的元素总是保持单调递增. set<int> a; set的插入 set没有尾部插入函数push_back(),元素的插入一般使用insert进行动态检索插入. a ...

  8. nginx反向代理proxy&lowbar;set&lowbar;header自定义header头无效

    公司使用nginx作为负载均衡,有时候需要自定义header头发送给后端的真实服务器. 想过去应该是非常的简单的事情. 例子如下: 设置代理服务器ip头   1 proxy_set_header X- ...

  9. LintCode-35&period;翻转链表

    翻转链表 翻转一个链表 样例 给出一个链表 1->2->3->null ,这个翻转后的链表为 3->2->1->null 挑战 在原地一次翻转完成 标签 链表 优步 ...

  10. 【循环节】 Codeforces Round &num;401 &lpar;Div&period; 2&rpar; A&period; 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}, ...