1699: 2^x mod n = 1

忘是亡心i 2024-02-18 22:16 19阅读 0赞

### **1699: 2^x mod n = 1** ###

时间限制: 1 Sec 内存限制: 32 MB  
提交: 14 解决: 11  
您该题的状态：**已完成**  
\[[提交][Link 1]\]\[[状态][Link 2]\]\[[讨论版][Link 3]\]

### **题目描述** ###

给你一个正整数n，要求你找到最小的x（x>0）满足2^x mod n = 1。

### **输入** ###

输入包含多组测试数据。每行一个正整数，代表n的值。

### **输出** ###

如果最小的x存在，则输出2^x mod n = 1（注意x和n要用具体的值代替），否则输出2^? mod n = 1。

### **样例输入** ###

<span style="color:#333333"><span style="color:black">2
    5</span></span>

### **样例输出** ###

<span style="color:#333333"><span style="color:black">2^? mod 2 = 1
    2^4 mod 5 = 1</span></span>

### **提示** ###

入门题

\#include<iostream>  
using namespace std;  
long long quick\_mod(int a,int b) 快速幂求解  
\{  
long long ans=1;  
  
while(b!=0)  
\{  
if(b%2==1)  
ans\*=a;  
a\*=a;  
b/=2;  
\}  
return ans;  
\}  
int main()  
\{  
int n,i,j,t;  
long long h=0;  
while(~scanf("%d",&n))  
\{  
for(i=1;i<100;i++)  
\{  
h=quick\_mod(2,i);  
if(h%n==1)  
\{  
cout<<"2^"<<i<<" mod "<<n<<" = 1"<<endl; 注意空格  
break;  
\}  
\}  
if(i==100)  
cout<<"2^?"<<" mod "<<n<<" = 1"<<endl;  
\}  
return 0;  
\}

[Link 1]: http://xyoj.xynu.edu.cn/submitpage.php?id=1699
[Link 2]: http://xyoj.xynu.edu.cn/problemstatus.php?id=1699
[Link 3]: http://xyoj.xynu.edu.cn/bbs.php?pid=1699

发表评论取消回复

表情：

评论列表（有 0 条评论，19人围观）

还没有评论，来说两句吧...

相关阅读

相关不外部定义函数编写程序，求1+X/1!+X^2/2!+x^3/3!+...+x^n/n!，并将结果存放到e，

下面是一个求求 1 X/1! X^2/2! x^3/3! ... x^n/n! 的程序，请注意，这个程序不使用外部定义函数：请输入要求的 n n = in

淩亂°似流年/ 2024年03月25日 15:18/ 0 赞/ 60 阅读

相关 1699: 2^x mod n = 1

1699: 2^x mod n = 1 时间限制: 1 Sec 内存限制: 32 MB 提交: 14 解决: 11 您该题的状态：已完成 \[[提交][Lin

忘是亡心i/ 2024年02月18日 22:16/ 0 赞/ 20 阅读

相关 MOD (ASCII (SUBSTR ('abcd', 1, 1)), 2)

一套连招：截取'abcd'的第一个元素转化为ASCII码取除以2的余数; select MOD (ASCII (SUBSTR ('abcd', 1, 1)), 2) fro

雨点打透心脏的1/2处/ 2023年06月25日 10:04/ 0 赞/ 13 阅读

相关求x从0到n，f(x)=x^2+1的和

《程序设计基础-c语言》杨莉刘鸿翔 ISBN-978-7-03-032903-5 p240 习题7 5.编写函数`sum(int n

亦凉/ 2023年02月12日 10:23/ 0 赞/ 10 阅读

相关 Python 数组切片操作 X[:,0]、X[:,1]、X[:,:,0]、X[:,:,1]、X[:,m:n]和X[:,:,m:n]

一维数组，一般\[a ：b\]，取左闭右开。若有两个冒号，即\[a：b：c\]，则c是步长（当步长为负时，从右到左索引，倒序取值）；二维数组\[a，b\]，a是行、b是列；

╰+哭是因爲堅強的太久メ/ 2023年01月16日 11:11/ 0 赞/ 188 阅读

相关 c语言输入正整数n计算1-22+33-4*4,用C语言编写“输入x，n的值，计算式子是S=X/2!+X^2/3!+X^3/4!+......+X^n/(n+1)!...

满意答案 ![02ae427d08e371d7e90d5b995e828d6d.png][] taozi890114 2013.11.22 ![02ae427d08e3

约定不等于承诺〃/ 2022年10月14日 14:56/ 0 赞/ 67 阅读

相关 Hdu 1395 2^x mod n = 1 (欧拉定理分解素因数)

先吐槽一下：考完试后第一天实验室就断网，简直不可思议。题意：给出n,找出最小的x使其满足2^x mod n = 1 思路：欧拉定理（费马小定理的欧拉推广）可得如果n为1或

阳光穿透心脏的1/2处/ 2022年09月19日 12:11/ 0 赞/ 160 阅读

相关两个数学公式1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6 && 1^3 + 2^3 + ... + n^3 = [n(n+1)/2]^2

这应该不是数论，而是计算几何吧 1 2 + 2 2 + . . . + n 2 = n ( n + 1 ) ( 2 n + 1 ) / 6 1^2 + 2^2 + ...

系统管理员/ 2022年08月31日 02:27/ 0 赞/ 271 阅读

相关 O(n)时间求出1~n对模MOD的逆元

转自：http://www.2cto.com/kf/201401/272375.html 新学的一个求逆元的方法： inv\[i\] = ( MOD - MOD / i )

淩亂°似流年/ 2022年08月25日 01:42/ 0 赞/ 127 阅读

相关 51Nod--1014 X^2 Mod P

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\!problemId=1014][http_www.51nod

迷南。/ 2022年06月14日 06:52/ 0 赞/ 131 阅读