poj 3358 Period of an Infinite Binary Expansion(数论:欧拉函数+快速幂取模)

本文主要是介绍poj 3358 Period of an Infinite Binary Expansion(数论:欧拉函数+快速幂取模),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

不太好理解题意的一道题

给出一个除式

要求找到对应二进制的循环起点和最小循环节长度

这里还考察了分数化小数的知识点。。。

这点不会难怪看题解都觉得很吃力尴尬

1/10

分数化小数的规律如下:

0.1 0.2 0.4 0.8 1.6 1.2 0.4(每次取左侧一位×2,如果大于10,小数位取1,再把这一位%10)

0    0    0   0    1    1    0

以1/10为例:1/10 2/10 4/10 8/10 16/10 32/10 64/10....

取模后:1/10 2/10 4/10 8/10 6/10 2/10 4/10 

这不就是个循环吗?循环节为4,循环起点为2,正好与题目相符。。如何去找循环节和循环起点?

由于是二进制,所以分子可以表示为2^x,而模数即q

2^x=2^y(mod q),2^x(2^(y-x)-1)=0(mod q),即p|2^x(2^(y-x)-1)

因为x^(y-1)-1为奇数,所以p|2^x

首先把q尽量整除2直到不能整除为止,这个步骤的次数就是满足原式最小的x,并得到q'。

2^(y-x)=1(mod q')

根据欧拉定理,t=y-x=phi(q')满足此式。

因为2^phi(q')和q'的最大公约数可能不为1

所以不一定是最小值,需要枚举phi(q')约数。

用int交就WA,用long long就过了

代码如下:

<span style="font-size:18px;">#include <cmath>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;char str[100];
vector<LL> vec;LL gcd(LL a, LL b) {return b ? gcd(b, a%b) : a;
}LL euler_phi(LL n) {LL ans = n;LL m = sqrt(n+0.5);for(LL i=2; i<=m; ++i) {if(n%i == 0) {n /= i;ans = ans/i*(i-1);while(n%i == 0)n /= i;}}if(n > 1)ans = ans/n*(n-1);return ans;
}void get_fac(LL n) {LL m = sqrt(n+0.5);for(LL i=1; i<=m; ++i) {if(n%i == 0) {vec.push_back(i);if(n/i != i)vec.push_back(n/i);}}
}LL pow_mod(LL a, LL b, LL m) {LL ans = 1;while(b) {if(b & 1) {ans = ans*a%m;}a = a*a%m;b >>= 1;}return ans%m;
}int main(void) {char ch;LL cas = 0, tmp, x, y, p, q;while(scanf("%s", str) != EOF) {vec.clear();sscanf(str, "%lld%c%lld", &p, &ch, &q);if(!p) {printf("Case #%lld: 1,1\n", ++cas);continue;}//printf("p = %d\tq = %d\n", p, q);tmp = gcd(p, q);p /= tmp;q /= tmp;x = 1;while(q % 2 == 0) {q >>= 1;++x;}tmp = euler_phi(q);get_fac(tmp);sort(vec.begin(), vec.end());for(int i=0; i<vec.size(); ++i) {if(pow_mod(2, vec[i], q) == 1) {y = vec[i];break;}}printf("Case #%lld: %lld,%lld\n", ++cas, x, y);}return 0;
}</span>



这篇关于poj 3358 Period of an Infinite Binary Expansion(数论:欧拉函数+快速幂取模)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL count()聚合函数详解

《MySQLcount()聚合函数详解》MySQL中的COUNT()函数,它是SQL中最常用的聚合函数之一,用于计算表中符合特定条件的行数,本文给大家介绍MySQLcount()聚合函数,感兴趣的朋... 目录核心功能语法形式重要特性与行为如何选择使用哪种形式?总结深入剖析一下 mysql 中的 COUNT

MySQL 中 ROW_NUMBER() 函数最佳实践

《MySQL中ROW_NUMBER()函数最佳实践》MySQL中ROW_NUMBER()函数,作为窗口函数为每行分配唯一连续序号,区别于RANK()和DENSE_RANK(),特别适合分页、去重... 目录mysql 中 ROW_NUMBER() 函数详解一、基础语法二、核心特点三、典型应用场景1. 数据分

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Python get()函数用法案例详解

《Pythonget()函数用法案例详解》在Python中,get()是字典(dict)类型的内置方法,用于安全地获取字典中指定键对应的值,它的核心作用是避免因访问不存在的键而引发KeyError错... 目录简介基本语法一、用法二、案例:安全访问未知键三、案例:配置参数默认值简介python是一种高级编

python 常见数学公式函数使用详解(最新推荐)

《python常见数学公式函数使用详解(最新推荐)》文章介绍了Python的数学计算工具,涵盖内置函数、math/cmath标准库及numpy/scipy/sympy第三方库,支持从基础算术到复杂数... 目录python 数学公式与函数大全1. 基本数学运算1.1 算术运算1.2 分数与小数2. 数学函数

Linux如何快速检查服务器的硬件配置和性能指标

《Linux如何快速检查服务器的硬件配置和性能指标》在运维和开发工作中,我们经常需要快速检查Linux服务器的硬件配置和性能指标,本文将以CentOS为例,介绍如何通过命令行快速获取这些关键信息,... 目录引言一、查询CPU核心数编程(几C?)1. 使用 nproc(最简单)2. 使用 lscpu(详细信

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

Python中help()和dir()函数的使用

《Python中help()和dir()函数的使用》我们经常需要查看某个对象(如模块、类、函数等)的属性和方法,Python提供了两个内置函数help()和dir(),它们可以帮助我们快速了解代... 目录1. 引言2. help() 函数2.1 作用2.2 使用方法2.3 示例(1) 查看内置函数的帮助(

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

Python中bisect_left 函数实现高效插入与有序列表管理

《Python中bisect_left函数实现高效插入与有序列表管理》Python的bisect_left函数通过二分查找高效定位有序列表插入位置,与bisect_right的区别在于处理重复元素时... 目录一、bisect_left 基本介绍1.1 函数定义1.2 核心功能二、bisect_left 与