Co-prime(hdu4135)
2024-08-31 17:13:02
Co-prime
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3313 Accepted Submission(s): 1286
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.
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
1 10 2
3 15 5
Sample Output
Case #1: 5
Case #2: 10
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
Recommend
思路：素数打表+容斥原理;
因为要求在[n，m]中与互质的数的个数。
先打表求素数，然后分解k，求出k由哪些素数组成，然后我们可以用容斥求出[n,m]中与k不互质的数，然后区间长度减下即可；
每个数的质因数个数不会超过20个。
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<stdlib.h>
5 #include<string.h>
6 #include<vector>
7 #include<queue>
8 #include<stack>
9 using namespace std;
10 long long gcd(long long n,long long m);
11 bool prime[100005];
12 int ans[100005];
13 int bns[100005];
14 int dd[100005];
15 typedef long long LL;
16 int main(void)
17 {
18 int i,j,k;
19 scanf("%d",&k);
20 int s;
21 LL n,m,x;
22 for(i=2; i<=1000; i++)
23 {
24 if(!prime[i])
25 {
26 for(j=i; i*j<=100000; j++)
27 {
28 prime[i*j]=true;
29 }
30 }
31 }
32 int cnt=0;
33 for(i=2; i<=100000; i++)
34 {
35 if(!prime[i])
36 {
37 ans[cnt++]=i;
38 }
39 }
40 for(s=1; s<=k; s++)
41 {
42 int uu=0;
43 memset(dd,0,sizeof(dd));
44 scanf("%lld %lld %lld",&n,&m,&x);
45 while(x>=1&&uu<cnt)
46 {
47 if(x%ans[uu]==0)
48 {
49 dd[ans[uu]]=1;
50 x/=ans[uu];
51 }
52 else
53 {
54 uu++;
55 }
56 }
57 int qq=0;
58 for(i=2; i<=100000; i++)
59 {
60 if(dd[i])
61 {
62 bns[qq++]=i;
63 }
64 }
65 if(x!=1)
66 bns[qq++]=x;
67 n--;
68
69 LL nn=0;
70 LL mm=0;
71 for(i=1; i<=(1<<qq)-1; i++)
72 {
73 int xx=0; LL sum=1;
74 int flag=0;
75 for(j=0; j<qq; j++)
76 {
77 if(i&(1<<j))
78 {
79 xx++;
80 LL cc=gcd(sum,bns[j]);
81 sum=sum/cc*bns[j];
82 if(sum>m)
83 {
84 flag=1;
85 break;
86 }
87 }
88 }
89 if(flag)
90 continue;
91 else
92 {
93 if(xx%2==0)
94 {
95 nn-=n/sum;
96 mm-=m/sum;
97 }
98 else
99 {
100 nn+=n/sum;
101 mm+=m/sum;
102 }
103 }
104 }m-=mm;n-=nn;
105 printf("Case #%d: ",s);
106 printf("%lld\n",m-n);
107 }
108 return 0;
109 }
110 long long gcd(long long n,long long m)
111 {
112 if(m==0)
113 return n;
114 else if(n%m==0)
115 return m;
116 else return gcd(m,n%m);
117 }
最新文章
- 1226关于count(*)不走主键索引反而走二级索引
- sqlserver如何创建镜像图文教程（转）
- ReportingService报表入门
- Android开发环境
- mybatis配置问题
- java pio项目使用
- mm/vmalloc.c
- 【转】STM32定时器输出比较模式中的疑惑
- 足球运动训练心得及经验分析-c语言学习调查
- java生成验证码的逻辑
- struts2视频学习笔记 03-06（Struts 2配置文件无提示问题，Action配置中的各项默认值，各种转发类型）
- iOS9下修改回HTTP模式进行网络请求
- 带中文索引的ListView 仿微信联系人列表
- hdu1753()模拟大型实景数字相加
- 定制化Azure站点Java运行环境(3)
- QuartusII13.0使用教程详解（一个完整的工程建立）
- 10个经典的Java面试题集合（转载）
- 用 CSS3 做一个流星雨动画
- Linux显示更新十次后退出
- Java8-2-Lambda表达式实战-一句话实现Map中按照Value排序
热门文章
- 突破冯·诺依曼架构瓶颈！全球首款存算一体AI芯片诞生
- [Emlog主题] Monkey V3.0 优化修改
- 论文解读（GraRep）《GraRep: Learning Graph Representations with Global Structural Information》
- ceph块存储场景
- Android消除Toast延迟显示
- Linux基础命令---mput上传ftp文件
- class.getName()和class.getSimpleName()的区别
- 【Linux】【Services】【Configuration】puppet
- BigDecimal中要注意的一些事
- ssm中的模糊查询