Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

HDU1395 2^x mod n = 1——积与余数的性质

乌克兰大野猪 2019-08-12 12:33:00 阅读数:13 评论数:0 点赞数:0 收藏数:0

对于数论的学习比较的碎片化,所以开了一篇随笔来记录一下学习中遇到的一些坑,主要通过题目来讲解

本题围绕:积与余数

HDU1395 2^x mod n = 1

 

题目描述

输入一个数n,如果存在2的x次方mod输出的n余数为1,则输出2^x mod n = 1,否则输出2^? mod n = 1,其中n替换为每次输出的n的具体数值

输入

正整数n,读取到文件尾

输出

2^x mod n = 1或者2^? mod n = 1

样例输入

2
5

样例输出

2^? mod 2 = 1 
2^4 mod 5 = 1

题目分析

对于本题,要注意的点有:首先对于x的范围题目是没有给出的,所以不能想当然的假设把2^x设定在int或者long long的范围内用空间换时间的方法去做(对不起我踩坑了),再者,对于本题有一个概念性的知识点:多个数的积取余数等于这几个数分别取余数后的积的余数(几个数积的余数等于这几个数的余数的积的余数),这个概念可以使我们对一些情况进行优化,使得在计算很大的数的余数的时候不会溢出

代码:

 

 #include<iostream>
 #include<stdio.h>
 using namespace std;
 
 int main(){
     int n;
     while(scanf("%d", &n) != EOF){
         if(n ==  || n %  == ) printf("2^? mod %d = 1\n", n);        //偶数mod偶数余数不可能为1 任何数mod1 == 0 
         else{
             int x = ;
             int ans = ;
             while(true){            //每次都将x * 2,然后对于x mod n(几个数积的余数等于这几个数余数的积的余数) 
                 x *= ;                //这样使得在数很大的时候不会溢出 
                 ans++;
                 if(x % n == ){
                     printf("2^%d mod %d = 1\n", ans, n);        
                     break;
                 }else{
                     x %= n;
                 }
             }
         }
     }
     return ;
 }

 

版权声明
本文为[乌克兰大野猪]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/findview/p/11338973.html