博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
密码箱
阅读量:5733 次
发布时间:2019-06-18

本文共 1394 字,大约阅读时间需要 4 分钟。

 

在一次偶然的情况下,小可可得到了一个密码箱,听说里面藏着一份古代流传下来的藏宝图,只要能破解密码就能打开箱子,而箱子背面刻着的古代图标,就是对密码的提示。经过艰苦的破译,小可可发现,这些图标表示一个数以及这个数与密码的关系。假设这个数是n,密码为x,那么可以得到如下表述:

密码x大于0,且小于n,而x的平方除以n,得到的余数为1。

小可可知道满足上述条件的x可能不止一个,所以一定要把所有满足条件的x计算出来,密码肯定就在其中。计算的过程是很艰苦的,你能否编写一个程序来帮助小可可呢?(题中x,n均为正整数)

 

输入:输入文件只有一行,且只有一个数字n(1<=n<=2,000,000,000)。

输出:你的程序需要找到所有满足前面所描述条件的x,如果不存在这样的x,你的程序只需输出一行“None”(引号不输出),否则请按照从小到大的顺序输出这些x,每行一个数。

 

样例:

输入:

12

输出:

1

5

7

11

题目大意:求x2≡1(mod n)在x∈[1,n]的所有整数解.

做法:先将式子变形一下

X^2≡1(mod n) -> (x+1)(x-1)=kn(k∈Z)

对于任意解x,总有

X-1=pa

x+1=qb

X-1=qb

x+1=pa

其中ab=n且a<b.

分析可得x一定大于sqrt(n)小于n,a*b=n,其中之一大于sqrt(n),枚举所有可能的值,

这里注意对于每一个sqrt(n)->n内的b||a,总有一个a||b,小于sqrt(n)与其对应,所以   枚举1->sqrt(n),判断n/i可以压缩范围。

那莫我们将x+1取遍所有的b和k2,再将x?1取遍所有的b和k2即可不漏地得到所有解.

时间复杂度不会证…

1 #include
2 //#include
3 #include
4 #include
5 //#include
6 using namespace std; 7 int n; 8 int so[100000],len; 9 //vector
ans;10 int ans[100000],ls;11 int main(){12 freopen("box.in","r",stdin);freopen("box.out","w",stdout);13 scanf("%d",&n);14 int ss=(int)sqrt(n+0.5);15 for(int i=2;i<=ss;i++){16 if(n%i==0){17 so[++len]=n/i;18 }19 }20 so[++len]=n;21 for(int i=1;i<=len;i++){22 int t=so[i];23 for(int j=t;j<=n;j+=t){24 if((j+2)%(n/t)==0&&j+1!=1&&j+1
View Code

 

转载于:https://www.cnblogs.com/leni/p/4864992.html

你可能感兴趣的文章
iphone-common-codes-ccteam源代码 CCEncoding.m
查看>>
微信公众平台开发(96) 多个功能整合
查看>>
[转]MVC4项目中验证用户登录一个特性就搞定
查看>>
用Perl编写Apache模块续二 - SVN动态鉴权实现SVNAuth 禅道版
查看>>
Android 阴影,圆形的Button
查看>>
C++概述
查看>>
卡特兰数
查看>>
006_mac osx 应用跨屏幕
查看>>
nginx中配置文件的讲解
查看>>
MindNode使用
查看>>
SQL Server 2016 Alwayson新增功能
查看>>
HTTP库Axios
查看>>
CentOS7下安装python-pip
查看>>
认知计算 Cognitive Computing
查看>>
左手坐标系和右手坐标系 ZZ
查看>>
陀螺仪主要性能指标
查看>>
Java 架构师眼中的 HTTP 协议
查看>>
Linux 目录结构和常用命令
查看>>
Linux内存管理之mmap详解 (可用于android底层内存调试)
查看>>
利润表(年末)未分配利润公式备份
查看>>