HDU 1695 GCD (欧拉函数+容斥原理)

时间:2022-10-04 18:21:17

GCD

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4272    Accepted Submission(s): 1492

Problem Description
Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you're only required to output the total number of different number pairs.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.

Yoiu can assume that a = c = 1 in all test cases.

 
Input
The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases.
Each case contains five integers: a, b, c, d, k, 0 < a <= b <= 100,000, 0 < c <= d <= 100,000, 0 <= k <= 100,000, as described above.
 
Output
For each test case, print the number of choices. Use the format in the example.
 
Sample Input
2
1 3 1 5 1
1 11014 1 14409 9
 
Sample Output
Case 1: 9
Case 2: 736427
Hint

For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).

 
Source
 
Recommend
wangye
 

题意: 在1~a, 1~b中挑出(x,y)满足gcd(x,y) = k , 求(x,y) 的对数 , a,b<=10^5

思路: gcd(x, y) == k 说明x,y都能被k整除, 但是能被k整除的未必gcd=k  , 必须还要满足

互质关系. 问题就转化为了求1~a/k 和 1~b/k间互质对数的问题

可以把a设置为小的那个数, 那么以y>x来保持唯一性(题目要求, 比如[1,3] = [3,1] )

接下来份两种情况:

1. y <= a , 那么对数就是 1~a的欧拉函数的累计和(容易想到)

2. y >= a , 这个时候欧拉函数不能用了,怎么做?  可以用容斥原理,把y与1~a互质对数问题转换为

 /* ***********************************************
Author :kuangbin
Created Time :2013/8/19 22:08:43
File Name :F:\2013ACM练习\专题学习\数学\HDU\HDU1695GCD.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std; const int MAXN = ;
int prime[MAXN+];
void getPrime()
{
memset(prime,,sizeof(prime));
for(int i = ;i <= MAXN;i++)
{
if(!prime[i])prime[++prime[]] = i;
for(int j = ;j <= prime[] && prime[j] <= MAXN/i;j++)
{
prime[prime[j]*i] = ;
if(i%prime[j] == )break;
}
}
}
long long factor[][];
int fatCnt;
int getFactors(long long x)
{
fatCnt = ;
long long tmp = x;
for(int i = ; prime[i] <= tmp/prime[i];i++)
{
factor[fatCnt][] = ;
if(tmp%prime[i] == )
{
factor[fatCnt][] = prime[i];
while(tmp%prime[i] == )
{
factor[fatCnt][]++;
tmp /= prime[i];
}
fatCnt++;
}
}
if(tmp != )
{
factor[fatCnt][] = tmp;
factor[fatCnt++][] = ;
}
return fatCnt;
}
int euler[];
void getEuler()
{
memset(euler,,sizeof(euler));
euler[] = ;
for(int i = ;i <= ;i++)
if(!euler[i])
for(int j = i; j <= ;j += i)
{
if(!euler[j])
euler[j] = j;
euler[j] = euler[j]/i*(i-);
}
}
int calc(int n,int m)//n < m,求1-n内和m互质的数的个数
{
getFactors(m);
int ans = ;
for(int i = ;i < (<<fatCnt);i++)
{
int cnt = ;
int tmp = ;
for(int j = ;j < fatCnt;j++)
if(i&(<<j))
{
cnt++;
tmp *= factor[j][];
}
if(cnt&)ans += n/tmp;
else ans -= n/tmp;
}
return n - ans;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
getPrime();
int a,b,c,d;
int T;
int k;
scanf("%d",&T);
int iCase = ;
getEuler();
while(T--)
{
iCase++;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
if(k == || k > b || k > d)
{
printf("Case %d: 0\n",iCase);
continue;
}
if(b > d)swap(b,d);
b /= k;
d /= k;
long long ans = ;
for(int i = ;i <= b;i++)
ans += euler[i];
for(int i = b+;i <= d;i++)
ans += calc(b,i);
printf("Case %d: %I64d\n",iCase,ans);
} return ;
}

HDU 1695 GCD (欧拉函数+容斥原理)的更多相关文章

  1. hdu 1695 GCD &lpar;欧拉函数&plus;容斥原理&rpar;

    GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submiss ...

  2. HDU 1695 GCD 欧拉函数&plus;容斥原理&plus;质因数分解

    链接:http://acm.hdu.edu.cn/showproblem.php?pid=1695 题意:在[a,b]中的x,在[c,d]中的y,求x与y的最大公约数为k的组合有多少.(a=1, a ...

  3. HDU 1695 GCD &lpar;欧拉函数,容斥原理&rpar;

    GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submis ...

  4. HDU 1695 GCD 欧拉函数&plus;容斥定理

    输入a b c d k求有多少对x y 使得x在a-b区间 y在c-d区间 gcd(x, y) = k 此外a和c一定是1 由于gcd(x, y) == k 将b和d都除以k 题目转化为1到b/k 和 ...

  5. HDU 1695 GCD 欧拉函数&plus;容斥定理 &vert;&vert; 莫比乌斯反演

    GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submiss ...

  6. hdu 1695 GCD 欧拉函数 + 容斥

    http://acm.hdu.edu.cn/showproblem.php?pid=1695 要求[L1, R1]和[L2, R2]中GCD是K的个数.那么只需要求[L1, R1 / K]  和 [L ...

  7. HDU 2588 GCD &lpar;欧拉函数&rpar;

    GCD Time Limit: 1000MS   Memory Limit: 32768KB   64bit IO Format: %I64d & %I64u Submit Status De ...

  8. &lbrack;hdu1695&rsqb; GCD ——欧拉函数&plus;容斥原理

    题目 给定两个区间[1, b], [1, d],统计数对的个数(x, y)满足: \(x \in [1, b]\), \(y \in [1, d]\) ; \(gcd(x, y) = k\) HDU1 ...

  9. HDU 1695 GCD(欧拉函数&plus;容斥原理)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1695 题意:x位于区间[a, b],y位于区间[c, d],求满足GCD(x, y) = k的(x, ...

随机推荐

  1. urlrewrite伪静态 及多参数传递-附正则表达式语法 &lbrack;轉&rsqb;

    首先 加载 urlrewrite包 配置web.xml [list] [*] <error-page> [*]             <error-code>404</ ...

  2. Fiddler2汉化版使用说明

    fiddler是一款免费且功能强大的数据包抓取软件,它能够快速的抓取HTTP会话以及支持监视.还可设置断点等诸多实用功能,非常适合计算机工作者们分析数据使用.本文就为大家详细介绍一下fiddler的功 ...

  3. Mysql表操作

    查看表结构: 可以使用describe或show create table语句查看表的结构: describe表名; Show create table 表名; 修改表名: Alter table 旧 ...

  4. 【NodeJs】Ctrl&plus;C在Linux平台和Windows平台下的TCP连接中的不同表现

    Linux平台:CentOS release 6.5 (Final) Windows平台:Windows 7 旗舰版 服务器端代码如下: var net = require('net'); var s ...

  5. docker学习------swarm集群虚机异常关机,node状态为down

    1.因昨天虚机异常关闭,导致今天上去查看时,node节点状态显示为down 2.查了些相关资料,找到处理办法(因我的节点没有任何数据,所以直接对其进行清除) docker swarm leave -- ...

  6. Redis实战 - 5事务:multi、exec和watch

    介绍 redis的目标的是: 简洁,高效,由于事务本身就是一个很复杂的东西,所有我们不能把事务做的太复杂. DISCARD 取消事务,放弃执行事务块内的所有命令. EXEC 执行所有事务块内的命令. ...

  7. simple简单消息队列

    一:介绍 1.优缺点 简单,但是耦合性较高. 这种模式是生产者与消费者一一对应,就是一个产生者,有一个消费者来消费. 如果,多个消费者想消费一个队列中的消息就不适合了.这种情况在后面会接着介绍. 2. ...

  8. android学习:apiDemos导入时R&period;java无法生成的问题

    准备导入apiDemos研究一下别人的代码,发现导入后不能正常build,无法生成R.java,发现res/layout/progressbar_2.xml里有几个 <ProgressBar a ...

  9. gmtdefaults locate

    http://seisman.blog.ustc.edu.cn/index.php/archives/553

  10. 青客宝团队Consul内部分享ppt

    青客宝团队Consul内部分享ppt   https://mp.weixin.qq.com/s?src=3&timestamp=1503647705&ver=1&signatu ...