http://acm.hdu.edu.cn/showproblem.php?pid=1695
题意:求[a,b]和[c,d]中分别取一个数,问取到的两个数的gcd=k的对数!!其中(2,3)跟(3,2)这2种类型只算一种,视为重复
Sample Input
2
1 3 1 5 1
1 11014 1 14409 9
Sample Output
Case 1: 9
Case 2: 736427
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define eps 1e-8
#define PI 3.14159265358979
#define inf 0x3fffffff
#define L 100005
long long e[L];
int prime[L][20], num[L]; //prime[i][j]储存i的第j个质因子,num[i]储存i的质因子个数
void Euler ()
{
int i, j;
for (i = 1; i < L; i++) //初始化
e[i] = i;
for (i = 2; i < L; i++)
{
if (e[i] == i) //只有素数才可进来
{
e[i] = i - 1;
for (j = i << 1; j < L; j += i) //求欧拉的同时求质因子
e[j] = e[j] - e[j] / i, prime[j][num[j]++] = i;
}
}
for (i = 2; i < L; i++) //递推求和
e[i] += e[i-1];
}
int dfs (int x, int b, int n) //求[1,b]中有多少个与n非互质
{
if (!b)
return 0;
int ans = 0, i;
for (i = x; i < num[n]; i++)
ans += b/prime[n][i] - dfs (i+1, b/prime[n][i], n); //容斥原理
return ans;
}
int main()
{
int t, a, b, c, d, k, cc = 1, i;
long long res;
memset (num, 0, sizeof(num));
Euler ();
scanf ("%d", &t);
while (t--)
{
scanf ("%d%d%d%d%d", &a, &b, &c, &d, &k);
printf ("Case %d: ", cc++);
if (!k) //k==0下面作为分母会出大错
{
puts ("0");
continue;
}
b /= k, d /= k; //问题的转化,转化成求gcd=1的对数
if (d < b)
d ^= b, b ^= d, d ^= b;
res = e[b]; //[1,b]和[1,b]的gcd为1的对数
for (i = b + 1; i <= d; i++) //求[b+1,d]与[1,b]的互质对数
res += b - dfs (0, b, i); //已经无法用语言形容了,我反正信了
printf ("%I64d\n", res);
}
return 0;
}
分享到:
相关推荐
"hdu 1695 GCD(欧拉函数+容斥原理)" 题目大意是:给定 a, b, c, d, k,找到一队 x, y,满足 g(x, y) = k,且 x ∈ [1, b], y ∈ [1, d],问有多少对符合要求的 (x, y)。 思路是:gcd(x, y) == k 解释 x, y 都能...
街道级行政区划shp矢量数据,wgs84坐标系,下载直接使用
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
街道级行政区划shp矢量数据,wgs84坐标系,下载直接使用
轻量级密码算法LBlock的FPGA优化实现.docx
街道级行政区划shp矢量数据,wgs84坐标系,下载直接使用
Git 资料 progit-zh-v2.1.1.pdf
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
篮球计分器FPGA附程序..doc
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
内容概要:本文档全面介绍了Linux开发的基础知识、应用场景、环境搭建、常用命令、Shell脚本编程以及C/C++和Python开发等内容。首先阐述了Linux开发的重要性及其在服务器端开发、嵌入式开发和系统运维等领域的广泛应用。接着详细讲解了如何选择合适的Linux发行版并安装系统,配置开发环境,包括安装必要的开发工具和配置SSH服务。文档还深入讲解了Linux基础命令,如文件和目录操作、文件内容查看与编辑、进程管理和权限管理。此外,介绍了Shell脚本编程的基本语法,包括变量、条件语句、循环语句和函数定义。针对C/C++和Python开发,文档分别讲解了编译器安装、程序编写与编译、调试方法及使用虚拟环境等内容。最后,简要介绍了Linux内核开发的相关知识,包括下载编译内核、内核模块开发等,并推荐了相关学习资源。 适合人群:对Linux开发感兴趣的初学者及有一定经验的研发人员,尤其是希望深入掌握Linux开发技能的开发者。 使用场景及目标:①掌握Linux开发环境的搭建与配置;②熟悉Linux基础命令和Shell脚本编程;③学习C/C++和Python在Linux下的开发流程;④了解Linux内核开发的基本概念和技术。 阅读建议:此文档内容丰富,涵盖面广,建议读者根据自身需求选择性阅读,并结合实际操作进行练习。特别是对于初学者,应先掌握基础命令和开发环境的搭建,再逐步深入到编程语言和内核开发的学习。
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
街道级行政区划shp数据,wgs84坐标系,直接使用。
内容概要:本文档《word练习题.docx》是一份详细的Word操作练习指南,涵盖了从基础到高级的各种功能。文档分为三个主要部分:内容编辑、页面布局和高效文档。内容编辑部分包括文本格式化、段落设置、项目编号、制表位、边框与底纹等练习;页面布局部分涉及分节符、分栏、页眉页脚、水印等设置;高效文档部分则聚焦于样式管理、导航窗格、题注、书签、超级链接、脚注与尾注、交叉引用等功能。每个练习都有具体的操作步骤,帮助用户掌握Word的各种实用技巧。 适合人群:适用于Word初学者及希望提高Word技能的中级用户,尤其是需要频繁使用Word进行文档编辑和排版的办公人员。 使用场景及目标:①帮助用户熟悉Word的基本操作,如文本编辑、格式设置等;②提升用户的文档排版能力,学会设置复杂的页面布局;③提高工作效率,掌握高效文档管理技巧,如样式应用、题注和交叉引用等。 其他说明:此文档不仅提供了具体的练习题目,还附带了详细的步骤说明,用户可以根据指引逐步完成每个练习。此外,文档中的一些练习涉及到智能文档和Office智能客户端的应用,有助于用户了解Word在企业级应用中的潜力。建议用户按照章节顺序逐步学习,实践每一个练习,以达到最佳的学习效果。
街道级行政区划shp数据,wgs84坐标系,直接下载使用。
全球腐败感知数据(2000-2023)——3000行 33个指标 关于数据集 该数据集包含3000行和33列,涵盖了2000年至2023年的腐败感知指数(CPI)数据和各种治理指标。它包括国家排名、分数和其他指标,如公共部门腐败、司法腐败、贿赂指数、商业道德、民主指数、法治、政府效率、经济指标和人类发展指数。 这些数据可用于: 腐败趋势分析 腐败对GDP、人类发展指数和治理的影响 跨国比较 数据可视化和机器学习模型 该数据集对研究人员、数据分析师、政策制定者和对研究全球腐败趋势非常有用。
毕业设计(论文) 基于FPGA的数字频率计设计.doc
街道级行政区划shp数据,wgs84坐标系,直接使用。
NTI1NDU3NTAyODMwOTQxMzI0M18xNzQ0Nzk1MTk1OTgz_6.JPG