UVA106 - Fermat vs. Pythagoras(素勾股数)

2024-08-24 04:08

本文主要是介绍UVA106 - Fermat vs. Pythagoras(素勾股数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

UVA106 - Fermat vs. Pythagoras(素勾股数)

题目链接

题目大意:给你一个数n,勾股数三元组(x,y,z)的定义:满足x < y < z, x^2 + y^2 = z^2.现在问这里里面有多少个三元组是素勾股数即满足x,y, z两两互质。并且判断剩下的1-n的数有多少是没有出现在勾股数三元组中。

解题思路:先找出所有的素勾股数(x, y, z) ,那么便可以通过(kx, ky, kz)得到不是素勾股数的勾股数。接着要换种方式构造素勾股数,公式:x = m^2 - n^2; y = 2mn; z = m^2 + n^2;其中若 m 和 n 是互质,而且 m 和 n 其中有一个是偶数,计算出来的 x, y, z就是素勾股数。这样可以将遍历的范围缩小1000.

代码:

#include <cstdio>
#include <cstring>
#include <cmath>const int maxn = 1e6 + 5;int vis[maxn];
int n;int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}int solve () {int x, y, z;int m = sqrt(n);int count = 0;memset (vis, 0, sizeof (vis));for (int i = 1; i <= m; i++) {for (int j = i + 1; j <= m; j += 2) {x = j * j - i * i;y = 2 * i * j;z = j * j + i * i;if (x > n || y > n || z > n)continue;if (x * x + y * y == z * z && gcd(i, j) == 1) {//            printf ("%d %d %d\n", x, y, z);count++;for (int k = 1; k * z <= n; k++)vis[k * x] = vis[k * y] = vis[k * z] = 1;}}}return count;
}int main () {while (scanf ("%d", &n) == 1) {int c = solve();int p = 0;for (int i = 1; i <= n; i++)if (!vis[i]) {p++;
//                printf ("%d\n", i);}printf ("%d %d\n", c, p);}return 0;
}

这篇关于UVA106 - Fermat vs. Pythagoras(素勾股数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1101404

相关文章

Android平台播放RTSP流的几种方案探究(VLC VS ExoPlayer VS SmartPlayer)

技术背景 好多开发者需要遴选Android平台RTSP直播播放器的时候,不知道如何选的好,本文针对常用的方案,做个大概的说明: 1. 使用VLC for Android VLC Media Player(VLC多媒体播放器),最初命名为VideoLAN客户端,是VideoLAN品牌产品,是VideoLAN计划的多媒体播放器。它支持众多音频与视频解码器及文件格式,并支持DVD影音光盘,VCD影

VS Code 调试go程序的相关配置说明

用 VS code 调试Go程序需要在.vscode/launch.json文件中增加如下配置:  // launch.json{// Use IntelliSense to learn about possible attributes.// Hover to view descriptions of existing attributes.// For more information,

解决服务器VS Code中Jupyter突然崩溃的问题

问题 本来在服务器Anaconda的Python环境里装其他的包,装完了想在Jupyter里写代码验证一下有没有装好,一运行发现Jupyter崩溃了!?报错如下所示 Failed to start the Kernel. ImportError: /home/hujh/anaconda3/envs/mia/lib/python3.12/lib-dynload/_sqlite3.cpython-

VSC++: 括号对称比较

括号的使用规则:大括号,中括号,小括号{[()]};中括号,小括号[()];小括号();大括号、中括号、小括号、中括号、小括号、大括号{[()][()]};大括号,中括号,小括号,小括号{[(())]};大括号,中括号,小括号,小括号{[()()]};小括号不能嵌套,小括号可连续使用。 {[]}、{()}、([])、({})、[{}]、{}、[]、{[}]、[(])都属非法。 char aa[

Apache Kylin VS Apache Doris全方位对比

1 系统架构 1.1 What is Kylin1.2 What is Doris2 数据模型 2.1 Kylin的聚合模型2.2 Doris的聚合模型2.3 Kylin Cuboid VS Doris RollUp2.4 Doris的明细模型3 存储引擎4 数据导入5 查询6 精确去重7 元数据8 高性能9 高可用10 可维护性 10.1 部署10.2 运维10.3 客服11 易用性 11.1

vs环境下C++dll生成和使用

动态库和静态库: 动态库:全名动态链接库,用于将你的函数封装,让别人只能调用,不能看你的实现代码。由引入库和dll组成:引入库包含导出的函数和变量名,dll包含实际的函数和数据,运行时加载访问dll文件。  Windows API中的所有函数都封装在dll里面,最重要的三个: Kernel32.dll:包含管理内存、进程和线程的各个函数。User32.dll:包含用于执行用户界面任务,如窗口和

VS Code与SVN关联

VS Code是一款轻量级的集成开发环境,可通过安装插件与SVN进行关联。以下是将VS Code与SVN关联的步骤: 安装SVN插件:在VS Code中打开Extensions(快捷键:Ctrl+Shift+X),搜索并安装"svn"插件。 安装SVN命令行工具:在计算机上安装SVN命令行工具,确保在命令行中可以运行svn命令。 配置SVN路径:在VS Code中打开用户设置(快捷键:Ct

学习记录-VS踩坑记录

一、安装VS2015后,CMAKE执行错误: CMAKE_C_COMPILER-NOTFOUND" was not found.   CMAKE_CXX_COMPILER-NOTFOUND" was not found.  环境: 1.公司内网,无法上外网; 2.文件加密系统; 3.数字公司杀毒软件; 解决方法: 清理环境,添加USBwifi,安全模式卸载数字软件; 1.设置环

面试题41:和为s的两个数VS和为s的连续正数数列

问题说明: 1.和为s的两个数问题是从一个排序的数组中找出和为s的两个数; 2.原题是找出一个即可,现在全部找出; 3.和为s的连续正数数列是给定一个数找出所有连续正数数列的和为s,例如s为9,(2,3,4)就是其中一组。 (一)和为s的两个数问题 public static int findNumbersWithSum(int[] sorted, int fromIndex, in

vs中使用c#\sqlite数据库开发(1)

开发前: 之前在java开发中使用过sqlite,对它有些印象。在用winform或wpf开发小应用程序时,发现用sqlite数据库也是不错的。就像一个会员管理软件,开发完毕后,可以省去想sqlserver那些复杂的操作。软件安装时,不需要额外的数据库环境。简单、便捷。但对于大并发量、大数据量的开发就不要使用sqlite了。如果你用过h2数据库,可以对比一下两者的优劣。 开发前准备: 1.下